Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
The fragment assembly string graph
Beteiligte:
Myers, Eugene W.
Erschienen:
Oxford University Press (OUP), 2005
Erschienen in:Bioinformatics
Sprache:
Englisch
DOI:
10.1093/bioinformatics/bti1114
ISSN:
1367-4811;
1367-4803
Entstehung:
Anmerkungen:
Beschreibung:
<jats:title>Abstract</jats:title>
<jats:p>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.</jats:p>
<jats:p>Contact: gene@eecs.berkeley.edu</jats:p>