Improving the performance of minimizers and winnowing schemes.
Identifieur interne : 000C61 ( PubMed/Checkpoint ); précédent : 000C60; suivant : 000C62Improving the performance of minimizers and winnowing schemes.
Auteurs : Guillaume Marçais [États-Unis] ; David Pellow [Israël] ; Daniel Bork [États-Unis] ; Yaron Orenstein [États-Unis] ; Ron Shamir [Israël] ; Carl Kingsford [États-Unis]Source :
- Bioinformatics (Oxford, England) [ 1367-4811 ] ; 2017.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- methods : Genomics, Sequence Analysis, DNA.
- Algorithms, Genome, Human, Humans, Software.
Abstract
The minimizers scheme is a method for selecting k -mers from sequences. It is used in many bioinformatics software tools to bin comparable sequences or to sample a sequence in a deterministic fashion at approximately regular intervals, in order to reduce memory consumption and processing time. Although very useful, the minimizers selection procedure has undesirable behaviors (e.g. too many k -mers are selected when processing certain sequences). Some of these problems were already known to the authors of the minimizers technique, and the natural lexicographic ordering of k -mers used by minimizers was recognized as their origin. Many software tools using minimizers employ ad hoc variations of the lexicographic order to alleviate those issues.
DOI: 10.1093/bioinformatics/btx235
PubMed: 28881970
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
pubmed:28881970Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improving the performance of minimizers and winnowing schemes.</title><author><name sortKey="Marcais, Guillaume" sort="Marcais, Guillaume" uniqKey="Marcais G" first="Guillaume" last="Marçais">Guillaume Marçais</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Pellow, David" sort="Pellow, David" uniqKey="Pellow D" first="David" last="Pellow">David Pellow</name><affiliation wicri:level="1"><nlm:affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv</wicri:regionArea><wicri:noRegion>Tel-Aviv</wicri:noRegion></affiliation></author><author><name sortKey="Bork, Daniel" sort="Bork, Daniel" uniqKey="Bork D" first="Daniel" last="Bork">Daniel Bork</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name><affiliation wicri:level="2"><nlm:affiliation>Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA</wicri:regionArea><placeName><region type="state">Massachusetts</region></placeName></affiliation></author><author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name><affiliation wicri:level="1"><nlm:affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv</wicri:regionArea><wicri:noRegion>Tel-Aviv</wicri:noRegion></affiliation></author><author><name sortKey="Kingsford, Carl" sort="Kingsford, Carl" uniqKey="Kingsford C" first="Carl" last="Kingsford">Carl Kingsford</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2017">2017</date><idno type="RBID">pubmed:28881970</idno><idno type="pmid">28881970</idno><idno type="doi">10.1093/bioinformatics/btx235</idno><idno type="wicri:Area/PubMed/Corpus">000B64</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000B64</idno><idno type="wicri:Area/PubMed/Curation">000B64</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000B64</idno><idno type="wicri:Area/PubMed/Checkpoint">000C61</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000C61</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Improving the performance of minimizers and winnowing schemes.</title><author><name sortKey="Marcais, Guillaume" sort="Marcais, Guillaume" uniqKey="Marcais G" first="Guillaume" last="Marçais">Guillaume Marçais</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Pellow, David" sort="Pellow, David" uniqKey="Pellow D" first="David" last="Pellow">David Pellow</name><affiliation wicri:level="1"><nlm:affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv</wicri:regionArea><wicri:noRegion>Tel-Aviv</wicri:noRegion></affiliation></author><author><name sortKey="Bork, Daniel" sort="Bork, Daniel" uniqKey="Bork D" first="Daniel" last="Bork">Daniel Bork</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author><author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name><affiliation wicri:level="2"><nlm:affiliation>Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA</wicri:regionArea><placeName><region type="state">Massachusetts</region></placeName></affiliation></author><author><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name><affiliation wicri:level="1"><nlm:affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</nlm:affiliation><country xml:lang="fr">Israël</country><wicri:regionArea>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv</wicri:regionArea><wicri:noRegion>Tel-Aviv</wicri:noRegion></affiliation></author><author><name sortKey="Kingsford, Carl" sort="Kingsford, Carl" uniqKey="Kingsford C" first="Carl" last="Kingsford">Carl Kingsford</name><affiliation wicri:level="4"><nlm:affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">Pittsburgh</settlement></placeName><orgName type="university">Université Carnegie-Mellon</orgName></affiliation></author></analytic><series><title level="j">Bioinformatics (Oxford, England)</title><idno type="eISSN">1367-4811</idno><imprint><date when="2017" type="published">2017</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Genome, Human</term><term>Genomics (methods)</term><term>Humans</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>Génome humain</term><term>Génomique ()</term><term>Humains</term><term>Logiciel</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Genomics</term><term>Sequence Analysis, DNA</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Genome, Human</term><term>Humans</term><term>Software</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Analyse de séquence d'ADN</term><term>Génome humain</term><term>Génomique</term><term>Humains</term><term>Logiciel</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The minimizers scheme is a method for selecting k -mers from sequences. It is used in many bioinformatics software tools to bin comparable sequences or to sample a sequence in a deterministic fashion at approximately regular intervals, in order to reduce memory consumption and processing time. Although very useful, the minimizers selection procedure has undesirable behaviors (e.g. too many k -mers are selected when processing certain sequences). Some of these problems were already known to the authors of the minimizers technique, and the natural lexicographic ordering of k -mers used by minimizers was recognized as their origin. Many software tools using minimizers employ ad hoc variations of the lexicographic order to alleviate those issues.</div></front></TEI><pubmed><MedlineCitation Status="MEDLINE" IndexingMethod="Curated" Owner="NLM"><PMID Version="1">28881970</PMID><DateCompleted><Year>2018</Year><Month>05</Month><Day>23</Day></DateCompleted><DateRevised><Year>2018</Year><Month>12</Month><Day>02</Day></DateRevised><Article PubModel="Print"><Journal><ISSN IssnType="Electronic">1367-4811</ISSN><JournalIssue CitedMedium="Internet"><Volume>33</Volume><Issue>14</Issue><PubDate><Year>2017</Year><Month>Jul</Month><Day>15</Day></PubDate></JournalIssue><Title>Bioinformatics (Oxford, England)</Title><ISOAbbreviation>Bioinformatics</ISOAbbreviation></Journal><ArticleTitle>Improving the performance of minimizers and winnowing schemes.</ArticleTitle><Pagination><MedlinePgn>i110-i117</MedlinePgn></Pagination><ELocationID EIdType="doi" ValidYN="Y">10.1093/bioinformatics/btx235</ELocationID><Abstract><AbstractText Label="Motivation" NlmCategory="UNASSIGNED">The minimizers scheme is a method for selecting k -mers from sequences. It is used in many bioinformatics software tools to bin comparable sequences or to sample a sequence in a deterministic fashion at approximately regular intervals, in order to reduce memory consumption and processing time. Although very useful, the minimizers selection procedure has undesirable behaviors (e.g. too many k -mers are selected when processing certain sequences). Some of these problems were already known to the authors of the minimizers technique, and the natural lexicographic ordering of k -mers used by minimizers was recognized as their origin. Many software tools using minimizers employ ad hoc variations of the lexicographic order to alleviate those issues.</AbstractText><AbstractText Label="Results" NlmCategory="UNASSIGNED">We provide an in-depth analysis of the effect of k -mer ordering on the performance of the minimizers technique. By using small universal hitting sets (a recently defined concept), we show how to significantly improve the performance of minimizers and avoid some of its worse behaviors. Based on these results, we encourage bioinformatics software developers to use an ordering based on a universal hitting set or, if not possible, a randomized ordering, rather than the lexicographic order. This analysis also settles negatively a conjecture (by Schleimer et al. ) on the expected density of minimizers in a random sequence.</AbstractText><AbstractText Label="Availability and Implementation" NlmCategory="UNASSIGNED">The software used for this analysis is available on GitHub: https://github.com/gmarcais/minimizers.git .</AbstractText><AbstractText Label="Contact" NlmCategory="UNASSIGNED">gmarcais@cs.cmu.edu or carlk@cs.cmu.edu.</AbstractText><CopyrightInformation>© The Author 2017. Published by Oxford University Press. All rights reserved. For Permissions, please e-mail: journals.permissions@oup.com</CopyrightInformation></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Marçais</LastName><ForeName>Guillaume</ForeName><Initials>G</Initials><AffiliationInfo><Affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Pellow</LastName><ForeName>David</ForeName><Initials>D</Initials><AffiliationInfo><Affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Bork</LastName><ForeName>Daniel</ForeName><Initials>D</Initials><AffiliationInfo><Affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Orenstein</LastName><ForeName>Yaron</ForeName><Initials>Y</Initials><AffiliationInfo><Affiliation>Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Shamir</LastName><ForeName>Ron</ForeName><Initials>R</Initials><AffiliationInfo><Affiliation>Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Kingsford</LastName><ForeName>Carl</ForeName><Initials>C</Initials><AffiliationInfo><Affiliation>Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA, USA.</Affiliation></AffiliationInfo></Author></AuthorList><Language>eng</Language><GrantList CompleteYN="Y"><Grant><GrantID>R01 GM122935</GrantID><Acronym>GM</Acronym><Agency>NIGMS NIH HHS</Agency><Country>United States</Country></Grant><Grant><GrantID>R01 HG007104</GrantID><Acronym>HG</Acronym><Agency>NHGRI NIH HHS</Agency><Country>United States</Country></Grant></GrantList><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType></PublicationTypeList></Article><MedlineJournalInfo><Country>England</Country><MedlineTA>Bioinformatics</MedlineTA><NlmUniqueID>9808944</NlmUniqueID><ISSNLinking>1367-4803</ISSNLinking></MedlineJournalInfo><CitationSubset>IM</CitationSubset><MeshHeadingList><MeshHeading><DescriptorName UI="D000465" MajorTopicYN="N">Algorithms</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D015894" MajorTopicYN="Y">Genome, Human</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D023281" MajorTopicYN="N">Genomics</DescriptorName><QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D006801" MajorTopicYN="N">Humans</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D017422" MajorTopicYN="N">Sequence Analysis, DNA</DescriptorName><QualifierName UI="Q000379" MajorTopicYN="Y">methods</QualifierName></MeshHeading><MeshHeading><DescriptorName UI="D012984" MajorTopicYN="Y">Software</DescriptorName></MeshHeading></MeshHeadingList></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="entrez"><Year>2017</Year><Month>9</Month><Day>9</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="pubmed"><Year>2017</Year><Month>9</Month><Day>9</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2018</Year><Month>5</Month><Day>24</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>ppublish</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">28881970</ArticleId><ArticleId IdType="pii">3953951</ArticleId><ArticleId IdType="doi">10.1093/bioinformatics/btx235</ArticleId><ArticleId IdType="pmc">PMC5870760</ArticleId></ArticleIdList><ReferenceList><Reference><Citation>J Comput Biol. 2004;11(4):734-52</Citation><ArticleIdList><ArticleId IdType="pubmed">15579242</ArticleId></ArticleIdList></Reference><Reference><Citation>Bioinformatics. 2016 Jun 15;32(12 ):i201-i208</Citation><ArticleIdList><ArticleId IdType="pubmed">27307618</ArticleId></ArticleIdList></Reference><Reference><Citation>J Comput Biol. 2015 May;22(5):336-52</Citation><ArticleIdList><ArticleId IdType="pubmed">25629448</ArticleId></ArticleIdList></Reference><Reference><Citation>Bioinformatics. 2004 Dec 12;20(18):3363-9</Citation><ArticleIdList><ArticleId IdType="pubmed">15256412</ArticleId></ArticleIdList></Reference><Reference><Citation>Bioinformatics. 2016 Jul 15;32(14 ):2103-10</Citation><ArticleIdList><ArticleId IdType="pubmed">27153593</ArticleId></ArticleIdList></Reference><Reference><Citation>Bioinformatics. 2015 May 15;31(10):1569-76</Citation><ArticleIdList><ArticleId IdType="pubmed">25609798</ArticleId></ArticleIdList></Reference><Reference><Citation>BMC Bioinformatics. 2012 Apr 19;13 Suppl 6:S1</Citation><ArticleIdList><ArticleId IdType="pubmed">22537038</ArticleId></ArticleIdList></Reference><Reference><Citation>Genome Biol. 2014 Mar 03;15(3):R46</Citation><ArticleIdList><ArticleId IdType="pubmed">24580807</ArticleId></ArticleIdList></Reference></ReferenceList></PubmedData></pubmed><affiliations><list><country><li>Israël</li><li>États-Unis</li></country><region><li>Massachusetts</li><li>Pennsylvanie</li></region><settlement><li>Pittsburgh</li></settlement><orgName><li>Université Carnegie-Mellon</li></orgName></list><tree><country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Marcais, Guillaume" sort="Marcais, Guillaume" uniqKey="Marcais G" first="Guillaume" last="Marçais">Guillaume Marçais</name></region><name sortKey="Bork, Daniel" sort="Bork, Daniel" uniqKey="Bork D" first="Daniel" last="Bork">Daniel Bork</name><name sortKey="Kingsford, Carl" sort="Kingsford, Carl" uniqKey="Kingsford C" first="Carl" last="Kingsford">Carl Kingsford</name><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name></country><country name="Israël"><noRegion><name sortKey="Pellow, David" sort="Pellow, David" uniqKey="Pellow D" first="David" last="Pellow">David Pellow</name></noRegion><name sortKey="Shamir, Ron" sort="Shamir, Ron" uniqKey="Shamir R" first="Ron" last="Shamir">Ron Shamir</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/PubMed/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C61 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PubMed/Checkpoint/biblio.hfd -nk 000C61 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= PubMed
|étape= Checkpoint
|type= RBID
|clé= pubmed:28881970
|texte= Improving the performance of minimizers and winnowing schemes.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Checkpoint/RBID.i -Sk "pubmed:28881970" \
| HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Checkpoint/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |