Fast Approximation of Frequent k-Mers and Applications to Metagenomics.
Identifieur interne : 000301 ( PubMed/Curation ); précédent : 000300; suivant : 000302Fast Approximation of Frequent k-Mers and Applications to Metagenomics.
Auteurs : Leonardo Pellegrina [Italie] ; Cinzia Pizzi [Italie] ; Fabio Vandin [Italie]Source :
- Journal of computational biology : a journal of computational molecular cell biology [ 1557-8666 ] ; 2019.
Abstract
Estimating the abundances of all k-mers in a set of biological sequences is a fundamental and challenging problem with many applications in biological analysis. Although several methods have been designed for the exact or approximate solution of this problem, they all require to process the entire data set, which can be extremely expensive for high-throughput sequencing data sets. Although in some applications it is crucial to estimate all k-mers and their abundances, in other situations it may be sufficient to report only frequent k-mers, which appear with relatively high frequency in a data set. This is the case, for example, in the computation of k-mers' abundance-based distances among data sets of reads, commonly used in metagenomic analyses. In this study, we develop, analyze, and test a sampling-based approach, called Sampling Algorithm for K-mErs approxIMAtion (SAKEIMA), to approximate the frequent k-mers and their frequencies in a high-throughput sequencing data set while providing rigorous guarantees on the quality of the approximation. SAKEIMA employs an advanced sampling scheme and we show how the characterization of the Vapnik-Chervonenkis dimension, a core concept from statistical learning theory, of a properly defined set of functions leads to practical bounds on the sample size required for a rigorous approximation. Our experimental evaluation shows that SAKEIMA allows to rigorously approximate frequent k-mers by processing only a fraction of a data set and that the frequencies estimated by SAKEIMA lead to accurate estimates of k-mer-based distances between high-throughput sequencing data sets. Overall, SAKEIMA is an efficient and rigorous tool to estimate k-mers' abundances providing significant speedups in the analysis of large sequencing data sets.
DOI: 10.1089/cmb.2019.0314
PubMed: 31891535
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000301
Links to Exploration step
pubmed:31891535Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Fast Approximation of Frequent <i>k</i>-Mers and Applications to Metagenomics.</title><author><name sortKey="Pellegrina, Leonardo" sort="Pellegrina, Leonardo" uniqKey="Pellegrina L" first="Leonardo" last="Pellegrina">Leonardo Pellegrina</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author><author><name sortKey="Pizzi, Cinzia" sort="Pizzi, Cinzia" uniqKey="Pizzi C" first="Cinzia" last="Pizzi">Cinzia Pizzi</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author><author><name sortKey="Vandin, Fabio" sort="Vandin, Fabio" uniqKey="Vandin F" first="Fabio" last="Vandin">Fabio Vandin</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2019">2019</date><idno type="RBID">pubmed:31891535</idno><idno type="pmid">31891535</idno><idno type="doi">10.1089/cmb.2019.0314</idno><idno type="wicri:Area/PubMed/Corpus">000301</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000301</idno><idno type="wicri:Area/PubMed/Curation">000301</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000301</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Fast Approximation of Frequent <i>k</i>-Mers and Applications to Metagenomics.</title><author><name sortKey="Pellegrina, Leonardo" sort="Pellegrina, Leonardo" uniqKey="Pellegrina L" first="Leonardo" last="Pellegrina">Leonardo Pellegrina</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author><author><name sortKey="Pizzi, Cinzia" sort="Pizzi, Cinzia" uniqKey="Pizzi C" first="Cinzia" last="Pizzi">Cinzia Pizzi</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author><author><name sortKey="Vandin, Fabio" sort="Vandin, Fabio" uniqKey="Vandin F" first="Fabio" last="Vandin">Fabio Vandin</name><affiliation wicri:level="1"><nlm:affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</nlm:affiliation><country xml:lang="fr">Italie</country><wicri:regionArea>Department of Information Engineering, University of Padova, Padova</wicri:regionArea></affiliation></author></analytic><series><title level="j">Journal of computational biology : a journal of computational molecular cell biology</title><idno type="eISSN">1557-8666</idno><imprint><date when="2019" type="published">2019</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Estimating the abundances of all <i>k</i>-mers in a set of biological sequences is a fundamental and challenging problem with many applications in biological analysis. Although several methods have been designed for the exact or approximate solution of this problem, they all require to process the entire data set, which can be extremely expensive for high-throughput sequencing data sets. Although in some applications it is crucial to estimate all <i>k</i>-mers and their abundances, in other situations it may be sufficient to report only <i>frequent k</i>-mers, which appear with relatively high frequency in a data set. This is the case, for example, in the computation of <i>k</i>-mers' abundance-based distances among data sets of reads, commonly used in metagenomic analyses. In this study, we develop, analyze, and test a sampling-based approach, called Sampling Algorithm for <i>K</i>-mErs approxIMAtion (SAKEIMA), to approximate the frequent <i>k</i>-mers and their frequencies in a high-throughput sequencing data set while providing rigorous guarantees on the quality of the approximation. SAKEIMA employs an advanced sampling scheme and we show how the characterization of the Vapnik-Chervonenkis dimension, a core concept from statistical learning theory, of a properly defined set of functions leads to practical bounds on the sample size required for a rigorous approximation. Our experimental evaluation shows that SAKEIMA allows to rigorously approximate frequent <i>k</i>-mers by processing only a fraction of a data set and that the frequencies estimated by SAKEIMA lead to accurate estimates of <i>k</i>-mer-based distances between high-throughput sequencing data sets. Overall, SAKEIMA is an efficient and rigorous tool to estimate <i>k</i>-mers' abundances providing significant speedups in the analysis of large sequencing data sets.</div></front></TEI><pubmed><MedlineCitation Status="Publisher" Owner="NLM"><PMID Version="1">31891535</PMID><DateRevised><Year>2019</Year><Month>12</Month><Day>31</Day></DateRevised><Article PubModel="Print-Electronic"><Journal><ISSN IssnType="Electronic">1557-8666</ISSN><JournalIssue CitedMedium="Internet"><PubDate><Year>2019</Year><Month>Dec</Month><Day>20</Day></PubDate></JournalIssue><Title>Journal of computational biology : a journal of computational molecular cell biology</Title><ISOAbbreviation>J. Comput. Biol.</ISOAbbreviation></Journal><ArticleTitle>Fast Approximation of Frequent <i>k</i>-Mers and Applications to Metagenomics.</ArticleTitle><ELocationID EIdType="doi" ValidYN="Y">10.1089/cmb.2019.0314</ELocationID><Abstract><AbstractText>Estimating the abundances of all <i>k</i>-mers in a set of biological sequences is a fundamental and challenging problem with many applications in biological analysis. Although several methods have been designed for the exact or approximate solution of this problem, they all require to process the entire data set, which can be extremely expensive for high-throughput sequencing data sets. Although in some applications it is crucial to estimate all <i>k</i>-mers and their abundances, in other situations it may be sufficient to report only <i>frequent k</i>-mers, which appear with relatively high frequency in a data set. This is the case, for example, in the computation of <i>k</i>-mers' abundance-based distances among data sets of reads, commonly used in metagenomic analyses. In this study, we develop, analyze, and test a sampling-based approach, called Sampling Algorithm for <i>K</i>-mErs approxIMAtion (SAKEIMA), to approximate the frequent <i>k</i>-mers and their frequencies in a high-throughput sequencing data set while providing rigorous guarantees on the quality of the approximation. SAKEIMA employs an advanced sampling scheme and we show how the characterization of the Vapnik-Chervonenkis dimension, a core concept from statistical learning theory, of a properly defined set of functions leads to practical bounds on the sample size required for a rigorous approximation. Our experimental evaluation shows that SAKEIMA allows to rigorously approximate frequent <i>k</i>-mers by processing only a fraction of a data set and that the frequencies estimated by SAKEIMA lead to accurate estimates of <i>k</i>-mer-based distances between high-throughput sequencing data sets. Overall, SAKEIMA is an efficient and rigorous tool to estimate <i>k</i>-mers' abundances providing significant speedups in the analysis of large sequencing data sets.</AbstractText></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Pellegrina</LastName><ForeName>Leonardo</ForeName><Initials>L</Initials><AffiliationInfo><Affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Pizzi</LastName><ForeName>Cinzia</ForeName><Initials>C</Initials><AffiliationInfo><Affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Vandin</LastName><ForeName>Fabio</ForeName><Initials>F</Initials><AffiliationInfo><Affiliation>Department of Information Engineering, University of Padova, Padova, Italy.</Affiliation></AffiliationInfo></Author></AuthorList><Language>eng</Language><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType></PublicationTypeList><ArticleDate DateType="Electronic"><Year>2019</Year><Month>12</Month><Day>20</Day></ArticleDate></Article><MedlineJournalInfo><Country>United States</Country><MedlineTA>J Comput Biol</MedlineTA><NlmUniqueID>9433358</NlmUniqueID><ISSNLinking>1066-5277</ISSNLinking></MedlineJournalInfo><CitationSubset>IM</CitationSubset><KeywordList Owner="NOTNLM"><Keyword MajorTopicYN="N">VC dimension</Keyword><Keyword MajorTopicYN="N">k-mer analysis</Keyword><Keyword MajorTopicYN="N">metagenomics</Keyword><Keyword MajorTopicYN="N">sampling algorithm</Keyword></KeywordList></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="entrez"><Year>2020</Year><Month>1</Month><Day>1</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="pubmed"><Year>2020</Year><Month>1</Month><Day>1</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2020</Year><Month>1</Month><Day>1</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>aheadofprint</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">31891535</ArticleId><ArticleId IdType="doi">10.1089/cmb.2019.0314</ArticleId></ArticleIdList></PubmedData></pubmed></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/PubMed/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000301 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PubMed/Curation/biblio.hfd -nk 000301 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= PubMed
|étape= Curation
|type= RBID
|clé= pubmed:31891535
|texte= Fast Approximation of Frequent k-Mers and Applications to Metagenomics.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Curation/RBID.i -Sk "pubmed:31891535" \
| HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Curation/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |