The fragment assembly string graph Export

@article{meyers:assembly, 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 10.1093/bioinformatics/bti1114}, address = {Department of Computer Science, University of California Berkeley, CA, USA. gene@eecs.berkeley.edu}, author = {Myers, Eugene W.}, citeulike-article-id = {2563094}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/bti1114}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/21/suppl_2/ii79?ijkey=c2db81aba4f315ae1b7aac89ba129ab325bfd273&keytype2=tf_ipsecsha}, citeulike-linkout-2 = {http://view.ncbi.nlm.nih.gov/pubmed/16204131}, citeulike-linkout-3 = {http://www.hubmed.org/display.cgi?uids=16204131}, day = {1}, doi = {10.1093/bioinformatics/bti1114}, issn = {1460-2059}, journal = {Bioinformatics}, keywords = {assembly, fragment, graph, thesis}, month = {September}, number = {suppl\_2}, pages = {ii79--85}, posted-at = {2008-05-19 16:21:45}, priority = {4}, title = {The fragment assembly string graph}, url = {http://dx.doi.org/10.1093/bioinformatics/bti1114}, volume = {21}, year = {2005} }

TY - JOUR ID - meyers:assembly L3 - citeulike-article-id:2563094 N2 - 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 10.1093/bioinformatics/bti1114 IS - suppl_2 JF - Bioinformatics SN - 1460-2059 AD - Department of Computer Science, University of California Berkeley, CA, USA. gene@eecs.berkeley.edu EP - 85 TI - The fragment assembly string graph VL - 21 SP - ii79 KW - assembly KW - fragment KW - graph KW - thesis AU - Myers, Eugene PY - 2005/09/01/ UR - http://dx.doi.org/10.1093/bioinformatics/bti1114 ER -