Read Mapping Algorithms for Single Molecule Sequencing Data
Identifieur interne : 000053 ( Istex/Curation ); précédent : 000052; suivant : 000054Read Mapping Algorithms for Single Molecule Sequencing Data
Auteurs : Vladimir Yanovsky [États-Unis] ; Stephen M. Rumble [États-Unis] ; Michael Brudno [Canada, États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Single Molecule Sequencing technologies such as the Heliscope simplify the preparation of DNA for sequencing, while sampling millions of reads in a day. Simultaneously, the technology suffers from a significantly higher error rate, ameliorated by the ability to sample multiple reads from the same location. In this paper we develop novel rapid alignment algorithms for two-pass Single Molecule Sequencing methods. We combine the Weighted Sequence Graph (WSG) representation of all optimal and near optimal alignments between the two reads sampled from a piece of DNA with k-mer filtering methods and spaced seeds to quickly generate candidate locations for the reads on the reference genome. We also propose a fast implementation of the Smith-Waterman algorithm using vectorized instructions that significantly speeds up the matching process. Our method combines these approaches in order to build an algorithm that is both fast and accurate, since it is able to take complete advantage of both of the reads sampled during two pass sequencing.
Url:
DOI: 10.1007/978-3-540-87361-7_4
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000053
Links to Exploration step
ISTEX:63B0B3D09E63D50AF88FCC4421631E51E4D51236Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Read Mapping Algorithms for Single Molecule Sequencing Data</title>
<author><name sortKey="Yanovsky, Vladimir" sort="Yanovsky, Vladimir" uniqKey="Yanovsky V" first="Vladimir" last="Yanovsky">Vladimir Yanovsky</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
<wicri:noCountry code="subField"> </wicri:noCountry>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: volodyan@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Rumble, Stephen M" sort="Rumble, Stephen M" uniqKey="Rumble S" first="Stephen M." last="Rumble">Stephen M. Rumble</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
<wicri:noCountry code="subField"> </wicri:noCountry>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: rumble@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Brudno, Michael" sort="Brudno, Michael" uniqKey="Brudno M" first="Michael" last="Brudno">Michael Brudno</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
<wicri:noCountry code="subField"> </wicri:noCountry>
</affiliation>
<affiliation wicri:level="4"><mods:affiliation>Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, </mods:affiliation>
<orgName type="university">Université de Toronto</orgName>
<country>Canada</country>
<placeName><settlement type="city">Toronto</settlement>
<region type="state">Ontario</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: brudno@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:63B0B3D09E63D50AF88FCC4421631E51E4D51236</idno>
<date when="2008" year="2008">2008</date>
<idno type="doi">10.1007/978-3-540-87361-7_4</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-C30M4TN0-8/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000053</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000053</idno>
<idno type="wicri:Area/Istex/Curation">000053</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Read Mapping Algorithms for Single Molecule Sequencing Data</title>
<author><name sortKey="Yanovsky, Vladimir" sort="Yanovsky, Vladimir" uniqKey="Yanovsky V" first="Vladimir" last="Yanovsky">Vladimir Yanovsky</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: volodyan@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Rumble, Stephen M" sort="Rumble, Stephen M" uniqKey="Rumble S" first="Stephen M." last="Rumble">Stephen M. Rumble</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: rumble@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Brudno, Michael" sort="Brudno, Michael" uniqKey="Brudno M" first="Michael" last="Brudno">Michael Brudno</name>
<affiliation><mods:affiliation>Department of Computer Science, </mods:affiliation>
</affiliation>
<affiliation wicri:level="4"><mods:affiliation>Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, </mods:affiliation>
<orgName type="university">Université de Toronto</orgName>
<country>Canada</country>
<placeName><settlement type="city">Toronto</settlement>
<region type="state">Ontario</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: brudno@cs.toronto.edu</mods:affiliation>
<country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Single Molecule Sequencing technologies such as the Heliscope simplify the preparation of DNA for sequencing, while sampling millions of reads in a day. Simultaneously, the technology suffers from a significantly higher error rate, ameliorated by the ability to sample multiple reads from the same location. In this paper we develop novel rapid alignment algorithms for two-pass Single Molecule Sequencing methods. We combine the Weighted Sequence Graph (WSG) representation of all optimal and near optimal alignments between the two reads sampled from a piece of DNA with k-mer filtering methods and spaced seeds to quickly generate candidate locations for the reads on the reference genome. We also propose a fast implementation of the Smith-Waterman algorithm using vectorized instructions that significantly speeds up the matching process. Our method combines these approaches in order to build an algorithm that is both fast and accurate, since it is able to take complete advantage of both of the reads sampled during two pass sequencing.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000053 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000053 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:63B0B3D09E63D50AF88FCC4421631E51E4D51236 |texte= Read Mapping Algorithms for Single Molecule Sequencing Data }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |