CoChat

The fragment assembly string graph

Myers, Eugene W. · 2005 · Bioinformatics

The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.

Abstract

We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes. Contact: gene@eecs.berkeley.edu

Overview

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/bti1114

Cites

16 of 16 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

  • The sequence of the human genome

    Venter, J. C., Adams, M. D., Myers, E. W., Li, P. W., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., et al. (2001) · Science · doi:10.1126/science.1058040 · Cited by 13,909

    Self-citation
  • Network Flows: Theory, Algorithms, and Applications.

    Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034 · cited 4×

    “Formally, a minimum cost network flow problem (Ahuja et al., 1993) is usually formulated as follows: In these terms our problem is as follows (where we have used a known transformation to convert the lower bounds into 0's by capturing them in the supply/demand values): The particularly simple…”
    BackgroundInfluential
  • The Genome Sequence of Drosophila melanogaster

    Adams, M. D., Celniker, S. E., Holt, R. A., Evans, C. A., Gocayne, J. D., Amanatides, P. G., Scherer, S. E., Li, P. W., Hoskins, R. A., Galle, R. F., et al. (2000) · Science · doi:10.1126/science.287.5461.2185 · Cited by 5,929 · cited 1×

    “…whole genome shotgun sequencing has become the prevailing paradigm for the first phase of sequencing an organism's genome (Weber and Myers, 1997; Adams et al., 2000; Venter et al., 2001) and routinely delivers 95–99% of the euchromatic sequence in large scaffolds of ordered and oriented contigs.”
    Background
  • Whole-Genome Shotgun Assembly and Analysis of the Genome of Fugu rubripes

    Aparicio, S., Chapman, J., Stupka, E., Putnam, N., Chia, J.-M., Dehal, P., Christoffels, A., Rash, S., Hoon, S., Smit, A., et al. (2002) · Science · doi:10.1126/science.1072104 · Cited by 1,591 · cited 1×

    “…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
    Background
  • A Whole-Genome Assembly of Drosophila

    Myers, E. W., Sutton, G. G., Delcher, A. L., Dew, I. M., Fasulo, D. P., Flanigan, M. J., Kravitz, S. A., Mobarry, C. M., Reinert, K. H. J., Remington, K. A., et al. (2000) · Science · doi:10.1126/science.287.5461.2196 · Cited by 1,538 · cited 1×

    “…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
    BackgroundSelf-citation
  • An Eulerian path approach to DNA fragment assembly

    Pevzner, P. A., Tang, H., & Waterman, M. S. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.171285098 · Cited by 1,352 · cited 1×

    “This approach was subsequently extended by Pevzner et al. (2001) of his research group giving rise to the Euler assembler.”
    Method
  • Genomic mapping by fingerprinting random clones: A mathematical analysis

    Lander, E. S., & Waterman, M. S. (1988) · Genomics · doi:10.1016/0888-7543(88)90007-9 · Cited by 961 · cited 2×

    “For example, an assembler that takes a 97% reconstruction and improves it to 99% is reducing the amount of unresolved sequence by a factor of three (from 3% to 1%) and, typically, improving contig sizes by a factor of 10 or more (by resolving 90% of the gaps) according to the Poisson statistical theory of sampling (La…”
    Method
  • A New Algorithm for DNA Sequence Assembly

    IDURY, R. M., & WATERMAN, M. S. (1995) · Journal of Computational Biology · doi:10.1089/cmb.1995.2.291 · Cited by 342 · cited 1×

    “In 1992 this author and Waterman–Idury presented two new ideas for fragment assembly in back to back talks at a DIMACs workshop on bioinformatics which were later published in the same volume of a journal (Myers, 1995; Idury and Waterman, 1995).”
    Background
  • Human Whole-Genome Shotgun Sequencing

    Weber, J. L., & Myers, E. W. (1997) · Genome Research · doi:10.1101/gr.7.5.401 · Cited by 311 · cited 2×

    “Paired-end whole genome shotgun sequencing has become the prevailing paradigm for the first phase of sequencing an organism’s genome (Weber and Myers, 1997; Adams et al., 2000; Venter et al., 2001) and routinely delivers 95–99% of the euchromatic sequence in large scaffolds of ordered and oriented contigs.”
    BackgroundSelf-citation
  • Whole-Genome Sequence Assembly for Mammalian Genomes: Arachne 2

    Jaffe, D. B., Butler, J., Gnerre, S., Mauceli, E., Lindblad-Toh, K., Mesirov, J. P., Zody, M. C., & Lander, E. S. (2003) · Genome Research · doi:10.1101/gr.828403 · Cited by 307 · cited 1×

    “…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
    Background

Show all 16 references

Cited by

Items 301–400 of 437

Metadata

Authors
Myers, E. W.
Affiliations
University of California, Berkeley (US)
Corresponding author
Myers, Eugene W.
Venue
Bioinformatics
Published
2005-09-01
Volume
21
Issue
suppl_2
Pages
ii79-ii85
ISSN
  • 1367-4803 (ISSN-L)
  • 1367-4811
OpenAlex
W2156104322
Cited by
424
References
16
Citations by year
2026: 8 · 2025: 14 · 2024: 16 · 2023: 19 · 2022: 19 · 2021: 27 · 2020: 28 · 2019: 37 · 2018: 28 · 2017: 34 · 2016: 37 · 2015: 22 · 2014: 24 · 2013: 22 · 2012: 28
FWCI
2.27
Type
journal article
Language
en
Open access
closed
Locations
  • Bioinformatics (publishedVersion)
  • PubMed (publishedVersion)
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
Keywords
string graphs, DNA sequence assembly, transitive reduction, de Bruijn graph, unitigs, whole genome assembly, mammalian genomes
MeSH terms
Algorithms, Base Sequence, Chromosome Mapping, Molecular Sequence Data, Sequence Analysis, DNA, DNA Fragmentation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.