title: Optimal assembly for high throughput shotgun sequencing.
abstract: We present a framework for the design of optimal assembly algorithms for shotgun sequencing under the criterion of complete reconstruction. We derive a lower bound on the read length and the coverage depth required for reconstruction in terms of the repeat statistics of the genome. Building on earlier works, we design a de Brujin graph based assembly algorithm which can achieve very close to the lower bound for repeat statistics of a wide range of sequenced genomes, including the GAGE datasets. The results are based on a set of necessary and sufficient conditions on the DNA sequence and the reads for reconstruction. The conditions can be viewed as the shotgun sequencing analogue of Ukkonen-Pevzner's necessary and sufficient conditions for Sequencing by Hybridization.
authors.affiliation: Department of EECS, UC Berkeley, California, USA. gbresler@eecs.berkeley.edu.
authors.forename: Guy
authors.initials: G
authors.lastname: Bresler
authors.forename: Ma'ayan
authors.initials: M
authors.lastname: Bresler
authors.forename: David
authors.initials: D
authors.lastname: Tse
mesh_terms: D000465:Algorithms; D020451:Contig Mapping; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*
references.citation: Bioinformatics. 2007 Feb 15;23(4):500-1
references.pmid: 17158514
references.citation: Bioinformatics. 2005 Sep 1;21 Suppl 2:ii79-85
references.pmid: 16204131
references.citation: Genome Res. 2008 May;18(5):821-9
references.pmid: 18349386
references.citation: J Comput Biol. 1995 Summer;2(2):275-90
references.pmid: 7497129
references.citation: Genome Biol. 2009;10(10):R103
references.pmid: 19796385
references.citation: Genome Res. 2011 Dec;21(12):2224-41
references.pmid: 21926179
references.citation: J Comput Biol. 2009 Aug;16(8):1101-16
references.pmid: 19645596
references.citation: Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53
references.pmid: 11504945
references.citation: Proc Natl Acad Sci U S A. 2011 Jan 25;108(4):1513-8
references.pmid: 21187386
references.citation: Genome Res. 1999 Sep;9(9):868-77
references.pmid: 10508846
references.citation: Nat Biotechnol. 2012 Jul 01;30(7):693-700
references.pmid: 22750884
references.citation: Genome Res. 2009 Jun;19(6):1117-23
references.pmid: 19251739
references.citation: J Comput Biol. 1995 Summer;2(2):291-306
references.pmid: 7497130
references.citation: Genomics. 1988 Apr;2(3):231-9
references.pmid: 3294162
references.citation: Nat Biotechnol. 2011 Nov 08;29(11):987-91
references.pmid: 22068540
references.citation: Genome Res. 2012 Mar;22(3):557-67
references.pmid: 22147368
references.citation: J Comput Biol. 2009 Jul;16(7):897-908
references.pmid: 19580519