SlideSort: all pairs similarity search for short reads
Identifieur interne : 002608 ( Main/Exploration ); précédent : 002607; suivant : 002609SlideSort: all pairs similarity search for short reads
Auteurs : Kana Shimizu ; Koji Tsuda [Japon]Source :
- Bioinformatics [ 1367-4803 ] ; 2010.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- methods : Computational Biology, Sequence Analysis, DNA.
- Algorithms, Base Sequence, Software.
Abstract
Url:
DOI: 10.1093/bioinformatics/btq677
PubMed: 21148542
PubMed Central: 3035798
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000B24
- to stream Pmc, to step Curation: 000B24
- to stream Pmc, to step Checkpoint: 001349
- to stream PubMed, to step Corpus: 001F20
- to stream PubMed, to step Curation: 001F20
- to stream PubMed, to step Checkpoint: 001D44
- to stream Ncbi, to step Merge: 000793
- to stream Ncbi, to step Curation: 000793
- to stream Ncbi, to step Checkpoint: 000793
- to stream Main, to step Merge: 002633
- to stream Main, to step Curation: 002608
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">SlideSort: all pairs similarity search for short reads</title>
<author><name sortKey="Shimizu, Kana" sort="Shimizu, Kana" uniqKey="Shimizu K" first="Kana" last="Shimizu">Kana Shimizu</name>
<affiliation><nlm:aff wicri:cut=" and" id="AFF1">Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST)</nlm:aff>
<wicri:noCountry code="subfield">National Institute of Advanced Industrial Science and Technology (AIST)</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Tsuda, Koji" sort="Tsuda, Koji" uniqKey="Tsuda K" first="Koji" last="Tsuda">Koji Tsuda</name>
<affiliation><nlm:aff wicri:cut=" and" id="AFF1">Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST)</nlm:aff>
<wicri:noCountry code="subfield">National Institute of Advanced Industrial Science and Technology (AIST)</wicri:noCountry>
</affiliation>
<affiliation wicri:level="1"><nlm:aff id="AFF1">ERATO Minato Project, Japan Science and Technology Agency, Japan</nlm:aff>
<country xml:lang="fr">Japon</country>
<wicri:regionArea>ERATO Minato Project, Japan Science and Technology Agency</wicri:regionArea>
<wicri:noRegion>Japan Science and Technology Agency</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">21148542</idno>
<idno type="pmc">3035798</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3035798</idno>
<idno type="RBID">PMC:3035798</idno>
<idno type="doi">10.1093/bioinformatics/btq677</idno>
<date when="2010">2010</date>
<idno type="wicri:Area/Pmc/Corpus">000B24</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000B24</idno>
<idno type="wicri:Area/Pmc/Curation">000B24</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000B24</idno>
<idno type="wicri:Area/Pmc/Checkpoint">001349</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">001349</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="RBID">pubmed:21148542</idno>
<idno type="wicri:Area/PubMed/Corpus">001F20</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">001F20</idno>
<idno type="wicri:Area/PubMed/Curation">001F20</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">001F20</idno>
<idno type="wicri:Area/PubMed/Checkpoint">001D44</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">001D44</idno>
<idno type="wicri:Area/Ncbi/Merge">000793</idno>
<idno type="wicri:Area/Ncbi/Curation">000793</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">000793</idno>
<idno type="wicri:doubleKey">1367-4803:2010:Shimizu K:slidesort:all:pairs</idno>
<idno type="wicri:Area/Main/Merge">002633</idno>
<idno type="wicri:Area/Main/Curation">002608</idno>
<idno type="wicri:Area/Main/Exploration">002608</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">SlideSort: all pairs similarity search for short reads</title>
<author><name sortKey="Shimizu, Kana" sort="Shimizu, Kana" uniqKey="Shimizu K" first="Kana" last="Shimizu">Kana Shimizu</name>
<affiliation><nlm:aff wicri:cut=" and" id="AFF1">Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST)</nlm:aff>
<wicri:noCountry code="subfield">National Institute of Advanced Industrial Science and Technology (AIST)</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Tsuda, Koji" sort="Tsuda, Koji" uniqKey="Tsuda K" first="Koji" last="Tsuda">Koji Tsuda</name>
<affiliation><nlm:aff wicri:cut=" and" id="AFF1">Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST)</nlm:aff>
<wicri:noCountry code="subfield">National Institute of Advanced Industrial Science and Technology (AIST)</wicri:noCountry>
</affiliation>
<affiliation wicri:level="1"><nlm:aff id="AFF1">ERATO Minato Project, Japan Science and Technology Agency, Japan</nlm:aff>
<country xml:lang="fr">Japon</country>
<wicri:regionArea>ERATO Minato Project, Japan Science and Technology Agency</wicri:regionArea>
<wicri:noRegion>Japan Science and Technology Agency</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j">Bioinformatics</title>
<idno type="ISSN">1367-4803</idno>
<idno type="eISSN">1367-4811</idno>
<imprint><date when="2010">2010</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Base Sequence</term>
<term>Computational Biology (methods)</term>
<term>Sequence Analysis, DNA (methods)</term>
<term>Software</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence d'ADN ()</term>
<term>Biologie informatique ()</term>
<term>Logiciel</term>
<term>Séquence nucléotidique</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
<term>Sequence Analysis, DNA</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Base Sequence</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence d'ADN</term>
<term>Biologie informatique</term>
<term>Logiciel</term>
<term>Séquence nucléotidique</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><p><bold>Motivation:</bold>
Recent progress in DNA sequencing technologies calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount of short reads. Searching similar pairs from a string pool is a fundamental process of <italic>de novo</italic>
genome assembly, genome-wide alignment and other important analyses.</p>
<p><bold>Results:</bold>
In this study, we designed and implemented an exact algorithm <italic>SlideSort</italic>
that finds all similar pairs from a string pool in terms of edit distance. Using an efficient pattern growth algorithm, <italic>SlideSort</italic>
discovers chains of common <italic>k</italic>
-mers to narrow down the search. Compared to existing methods based on single <italic>k</italic>
-mers, our method is more effective in reducing the number of edit distance calculations. In comparison to backtracking methods such as BWA, our method is much faster in finding remote matches, scaling easily to tens of millions of sequences. Our software has an additional function of single link clustering, which is useful in summarizing short reads for further processing.</p>
<p><bold>Availability:</bold>
Executable binary files and C++ libraries are available at <ext-link ext-link-type="uri" xlink:href="http://www.cbrc.jp/~shimizu/slidesort/">http://www.cbrc.jp/~shimizu/slidesort/</ext-link>
for Linux and Windows.</p>
<p><bold>Contact:</bold>
<email>slidesort@m.aist.go.jp</email>
; <email>shimizu-kana@aist.go.jp</email>
</p>
<p><bold>Supplementary information:</bold>
<ext-link ext-link-type="uri" xlink:href="http://bioinformatics.oxfordjournals.org/cgi/content/full/btq677/DC1">Supplementary data</ext-link>
are available at <italic>Bioinformatics</italic>
online.</p>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Abouelhoda, M" uniqKey="Abouelhoda M">M. Abouelhoda</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Burkhardt, S" uniqKey="Burkhardt S">S. Burkhardt</name>
</author>
<author><name sortKey="K Rkk Inen, J" uniqKey="K Rkk Inen J">J. Kärkkäinen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gower, J" uniqKey="Gower J">J. Gower</name>
</author>
<author><name sortKey="Ross, G" uniqKey="Ross G">G. Ross</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Han, J" uniqKey="Han J">J. Han</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Jiang, H" uniqKey="Jiang H">H. Jiang</name>
</author>
<author><name sortKey="Wong, W H" uniqKey="Wong W">W.H. Wong</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kruskal, J B" uniqKey="Kruskal J">J.B. Kruskal</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Langmead, B" uniqKey="Langmead B">B. Langmead</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H. Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R. Durbin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, R" uniqKey="Li R">R. Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lipman, D J" uniqKey="Lipman D">D.J. Lipman</name>
</author>
<author><name sortKey="Pearson, W R" uniqKey="Pearson W">W.R. Pearson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Manning, C" uniqKey="Manning C">C. Manning</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Prim, R" uniqKey="Prim R">R. Prim</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Qu, W" uniqKey="Qu W">W. Qu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S. Rajasekaran</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sagot, M F" uniqKey="Sagot M">M.-F. Sagot</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Simpson, J T" uniqKey="Simpson J">J.T. Simpson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tarjan, R" uniqKey="Tarjan R">R. Tarjan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Trapnell, C" uniqKey="Trapnell C">C. Trapnell</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Uno, T" uniqKey="Uno T">T. Uno</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Warren, R L" uniqKey="Warren R">R.L. Warren</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Weese, D" uniqKey="Weese D">D. Weese</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zerbino, D R" uniqKey="Zerbino D">D.R. Zerbino</name>
</author>
<author><name sortKey="Birney, E" uniqKey="Birney E">E. Birney</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<affiliations><list><country><li>Japon</li>
</country>
</list>
<tree><noCountry><name sortKey="Shimizu, Kana" sort="Shimizu, Kana" uniqKey="Shimizu K" first="Kana" last="Shimizu">Kana Shimizu</name>
</noCountry>
<country name="Japon"><noRegion><name sortKey="Tsuda, Koji" sort="Tsuda, Koji" uniqKey="Tsuda K" first="Koji" last="Tsuda">Koji Tsuda</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002608 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002608 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Main |étape= Exploration |type= RBID |clé= PMC:3035798 |texte= SlideSort: all pairs similarity search for short reads }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:21148542" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |