Maximum Likelihood Genome Assembly
Open accessThe DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Abstract
Whole genome shotgun assembly is the process of taking many short sequenced segments (reads) and reconstructing the genome from which they originated. We demonstrate how the technique of bidirected network flow can be used to explicitly model the double-stranded nature of DNA for genome assembly. By combining an algorithm for the Chinese Postman Problem on bidirected graphs with the construction of a bidirected de Bruijn graph, we are able to find the shortest double-stranded DNA sequence that contains a given set of k-long DNA molecules. This is the first exact polynomial time algorithm for the assembly of a double-stranded genome. Furthermore, we propose a maximum likelihood framework for assembling the genome that is the most likely source of the reads, in lieu of the standard maximum parsimony approach (which finds the shortest genome subject to some constraints). In this setting, we give a bidirected network flow-based algorithm that, by taking advantage of high coverage, accurately estimates the copy counts of repeats in a genome. Our second algorithm combines these predicted copy counts with matepair data in order to assemble the reads into contigs. We run our algorithms on simulated read data from Escherichia coli and predict copy counts with extremely high accuracy, while assembling long contigs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The fragment assembly string graph
Myers, E. W. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1114 · Cited by 424
Cited by
Progressive Cactus is a multiple-genome aligner for the thousand-genome era
Armstrong, J., Hickey, G., Diekhans, M., Fiddes, I. T., Novak, A. M., Deran, A., Fang, Q., Xie, D., Feng, S., Stiller, J., et al. (2020) · Nature · doi:10.1038/s41586-020-2871-y · Cited by 586
Assemblathon 1: A competitive assessment of de novo short read assembly methods
Earl, D., Bradnam, K., St. John, J., Darling, A., Lin, D., Fass, J., Yu, H. O. K., Buffalo, V., Zerbino, D. R., Diekhans, M., et al. (2011) · Genome Research · doi:10.1101/gr.126599.111 · Cited by 507
Novák, P., Neumann, P., & Macas, J. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-378 · Cited by 458
Genome graphs and the evolution of genome inference
Paten, B., Novak, A. M., Eizenga, J. M., & Garrison, E. (2017) · Genome Research · doi:10.1101/gr.214155.116 · Cited by 351
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly
Li, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts280 · Cited by 398
Metadata
- Authors
- Medvedev, P., & Brudno, M.
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2009-08
- Volume
- 16
- Issue
- 8
- Pages
- 1101-1116
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- OpenAlex
- W2035596374
- Cited by
- 110
- References
- 1
- FWCI
- 2.16
- Type
- journal article
- Language
- en
- Open access
- green
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.