Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds
Identifieur interne : 000246 ( Pmc/Curation ); précédent : 000245; suivant : 000247Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds
Auteurs : Laurent NoéSource :
- Algorithms for Molecular Biology : AMB [ 1748-7188 ] ; 2017.
Abstract
We expand the scope of work of Mak and Benson on single and multiple seeds by considering the Hit Integration model of Chung and Park (BMC Bioinform 11:31, 2010), demonstrate that the same dominance definition can be applied, and that a parameter-free study can be performed without any significant additional cost. We also consider two new discrete models, namely the Heaviside and the Dirac models, where lossless seeds can be integrated. From a theoretical standpoint, we establish a generic framework on all the proposed models, by applying a
Url:
DOI: 10.1186/s13015-017-0092-1
PubMed: 28289437
PubMed Central: 5310094
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000246
Links to Exploration step
PMC:5310094Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="Aff1"></nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">28289437</idno>
<idno type="pmc">5310094</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5310094</idno>
<idno type="RBID">PMC:5310094</idno>
<idno type="doi">10.1186/s13015-017-0092-1</idno>
<date when="2017">2017</date>
<idno type="wicri:Area/Pmc/Corpus">000246</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000246</idno>
<idno type="wicri:Area/Pmc/Curation">000246</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000246</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noé">Laurent Noé</name>
<affiliation><nlm:aff id="Aff1"></nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">Algorithms for Molecular Biology : AMB</title>
<idno type="eISSN">1748-7188</idno>
<imprint><date when="2017">2017</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p><italic>Spaced seeds</italic>
, also named <italic>gapped q-grams, gapped k-mers, spaced q-grams</italic>
, have been proven to be more sensitive than contiguous seeds (<italic>contiguous q-grams, contiguous k-mers</italic>
) in nucleic and amino-acid sequences analysis. Initially proposed to detect sequence similarities and to anchor sequence alignments, spaced seeds have more recently been applied in several <italic>alignment-free</italic>
related methods. Unfortunately, spaced seeds need to be initially designed. This task is known to be time-consuming due to the number of spaced seed candidates. Moreover, it can be altered by a set of <italic>arbitrary chosen</italic>
parameters from the probabilistic alignment models used. In this general context, <italic>Dominant seeds</italic>
have been introduced by Mak and Benson (Bioinformatics 25:302–308, 2009) on the Bernoulli model, in order to reduce the number of spaced seed candidates that are further processed in a <italic>parameter-free</italic>
calculation of the sensitivity.</p>
</sec>
<sec><title>Results</title>
<p>We expand the scope of work of Mak and Benson on single and multiple seeds by considering the Hit Integration model of Chung and Park (BMC Bioinform 11:31, 2010), demonstrate that the same dominance definition can be applied, and that a parameter-free study can be performed without any significant additional cost. We also consider two new discrete models, namely the Heaviside and the Dirac models, where lossless seeds can be integrated. From a theoretical standpoint, we establish a generic framework on all the proposed models, by applying a <italic>counting semi-ring</italic>
to quickly compute large polynomial coefficients needed by the <italic>dominance</italic>
filter. From a practical standpoint, we confirm that <italic>dominant seeds</italic>
reduce the set of, either single seeds to thoroughly analyse, or multiple seeds to store. Moreover, in <ext-link ext-link-type="uri" xlink:href="http://bioinfo.cristal.univ-lille.fr/yass/iedera%5fdominance">http://bioinfo.cristal.univ-lille.fr/yass/iedera_dominance</ext-link>
, we provide a full list of spaced seeds computed on the four aforementioned models, with one (continuous) parameter left free for each model, and with several (discrete) alignment lengths.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Mak, Dyf" uniqKey="Mak D">DYF Mak</name>
</author>
<author><name sortKey="Benson, G" uniqKey="Benson G">G Benson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chung, Wh" uniqKey="Chung W">WH Chung</name>
</author>
<author><name sortKey="Park, Sb" uniqKey="Park S">SB Park</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</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="Brejova, B" uniqKey="Brejova B">B Brejová</name>
</author>
<author><name sortKey="Brown, Dg" uniqKey="Brown D">DG Brown</name>
</author>
<author><name sortKey="Vina, T" uniqKey="Vina T">T Vinař</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Mak, Dyf" uniqKey="Mak D">DYF Mak</name>
</author>
<author><name sortKey="Gelfand, Y" uniqKey="Gelfand Y">Y Gelfand</name>
</author>
<author><name sortKey="Benson, G" uniqKey="Benson G">G Benson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chen, K" uniqKey="Chen K">K Chen</name>
</author>
<author><name sortKey="Zhu, Q" uniqKey="Zhu Q">Q Zhu</name>
</author>
<author><name sortKey="Yang, F" uniqKey="Yang F">F Yang</name>
</author>
<author><name sortKey="Tang, D" uniqKey="Tang D">D Tang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cs Ros, M" uniqKey="Cs Ros M">M Csűrös</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chen, W" uniqKey="Chen W">W Chen</name>
</author>
<author><name sortKey="Sung, Wk" uniqKey="Sung W">WK Sung</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yang, J" uniqKey="Yang J">J Yang</name>
</author>
<author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zhou, L" uniqKey="Zhou L">L Zhou</name>
</author>
<author><name sortKey="Stanton, J" uniqKey="Stanton J">J Stanton</name>
</author>
<author><name sortKey="Florea, L" uniqKey="Florea L">L Florea</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Frith, Mc" uniqKey="Frith M">MC Frith</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Kisman, D" uniqKey="Kisman D">D Kisman</name>
</author>
<author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sun, Y" uniqKey="Sun Y">Y Sun</name>
</author>
<author><name sortKey="Buhler, J" uniqKey="Buhler J">J Buhler</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Roytberg, Ma" uniqKey="Roytberg M">MA Roytberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Farach Colton, M" uniqKey="Farach Colton M">M Farach-Colton</name>
</author>
<author><name sortKey="Landau, Gm" uniqKey="Landau G">GM Landau</name>
</author>
<author><name sortKey="Cenk Sahinalp, S" uniqKey="Cenk Sahinalp S">S Cenk Sahinalp</name>
</author>
<author><name sortKey="Tsur, D" uniqKey="Tsur D">D Tsur</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kielbasa, Sm" uniqKey="Kielbasa S">SM Kiełbasa</name>
</author>
<author><name sortKey="Wan, R" uniqKey="Wan R">R Wan</name>
</author>
<author><name sortKey="Sato, K" uniqKey="Sato K">K Sato</name>
</author>
<author><name sortKey="Horton, P" uniqKey="Horton P">P Horton</name>
</author>
<author><name sortKey="Frith, Mc" uniqKey="Frith M">MC Frith</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Crochemore, M" uniqKey="Crochemore M">M Crochemore</name>
</author>
<author><name sortKey="Tischler, G" uniqKey="Tischler G">G Tischler</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Onodera, T" uniqKey="Onodera T">T Onodera</name>
</author>
<author><name sortKey="Shibuya, T" uniqKey="Shibuya T">T Shibuya</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Shrestha, Ams" uniqKey="Shrestha A">AMS Shrestha</name>
</author>
<author><name sortKey="Frith, Mc" uniqKey="Frith M">MC Frith</name>
</author>
<author><name sortKey="Horton, P" uniqKey="Horton P">P Horton</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Birol, I" uniqKey="Birol I">I Birol</name>
</author>
<author><name sortKey="Chu, J" uniqKey="Chu J">J Chu</name>
</author>
<author><name sortKey="Mohamadi, H" uniqKey="Mohamadi H">H Mohamadi</name>
</author>
<author><name sortKey="Jackman, Sd" uniqKey="Jackman S">SD Jackman</name>
</author>
<author><name sortKey="Raghavan, K" uniqKey="Raghavan K">K Raghavan</name>
</author>
<author><name sortKey="Vandervalk, Bp" uniqKey="Vandervalk B">BP Vandervalk</name>
</author>
<author><name sortKey="Raymond, A" uniqKey="Raymond A">A Raymond</name>
</author>
<author><name sortKey="Warren, Rl" uniqKey="Warren R">RL Warren</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Keich, U" uniqKey="Keich U">U Keich</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Nicolas, F" uniqKey="Nicolas F">F Nicolas</name>
</author>
<author><name sortKey="Rivals, E" uniqKey="Rivals E">É Rivals</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Yao, H" uniqKey="Yao H">H Yao</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schwartz, S" uniqKey="Schwartz S">S Schwartz</name>
</author>
<author><name sortKey="Kent, Wj" uniqKey="Kent W">WJ Kent</name>
</author>
<author><name sortKey="Smit, A" uniqKey="Smit A">A Smit</name>
</author>
<author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name>
</author>
<author><name sortKey="Baertsch, R" uniqKey="Baertsch R">R Baertsch</name>
</author>
<author><name sortKey="Hardison, Rc" uniqKey="Hardison R">RC Hardison</name>
</author>
<author><name sortKey="Haussler, D" uniqKey="Haussler D">D Haussler</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Lin, H" uniqKey="Lin H">H Lin</name>
</author>
<author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name>
</author>
<author><name sortKey="Zhang, Mq" uniqKey="Zhang M">MQ Zhang</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rumble, Sm" uniqKey="Rumble S">SM Rumble</name>
</author>
<author><name sortKey="Lacroute, P" uniqKey="Lacroute P">P Lacroute</name>
</author>
<author><name sortKey="Dalca, Av" uniqKey="Dalca A">AV Dalca</name>
</author>
<author><name sortKey="Fiume, M" uniqKey="Fiume M">M Fiume</name>
</author>
<author><name sortKey="Sidow, A" uniqKey="Sidow A">A Sidow</name>
</author>
<author><name sortKey="Brudno, M" uniqKey="Brudno M">M Brudno</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chen, Y" uniqKey="Chen Y">Y Chen</name>
</author>
<author><name sortKey="Souaiaia, T" uniqKey="Souaiaia T">T Souaiaia</name>
</author>
<author><name sortKey="Chen, T" uniqKey="Chen T">T Chen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Giladi, E" uniqKey="Giladi E">E Giladi</name>
</author>
<author><name sortKey="Healy, J" uniqKey="Healy J">J Healy</name>
</author>
<author><name sortKey="Myers, G" uniqKey="Myers G">G Myers</name>
</author>
<author><name sortKey="Hart, C" uniqKey="Hart C">C Hart</name>
</author>
<author><name sortKey="Kapranov, P" uniqKey="Kapranov P">P Kapranov</name>
</author>
<author><name sortKey="Lipson, D" uniqKey="Lipson D">D Lipson</name>
</author>
<author><name sortKey="Roels, S" uniqKey="Roels S">S Roels</name>
</author>
<author><name sortKey="Thayer, E" uniqKey="Thayer E">E Thayer</name>
</author>
<author><name sortKey="Letovsky, S" uniqKey="Letovsky S">S Letovsky</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="David, M" uniqKey="David M">M David</name>
</author>
<author><name sortKey="Dzamba, M" uniqKey="Dzamba M">M Dzamba</name>
</author>
<author><name sortKey="Lister, D" uniqKey="Lister D">D Lister</name>
</author>
<author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Brudno, M" uniqKey="Brudno M">M Brudno</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sovi, I" uniqKey="Sovi I">I Sović</name>
</author>
<author><name sortKey="Siki, M" uniqKey="Siki M">M Šikić</name>
</author>
<author><name sortKey="Wilm, A" uniqKey="Wilm A">A Wilm</name>
</author>
<author><name sortKey="Fenlon, Sn" uniqKey="Fenlon S">SN Fenlon</name>
</author>
<author><name sortKey="Chen, S" uniqKey="Chen S">S Chen</name>
</author>
<author><name sortKey="Nagarajan, N" uniqKey="Nagarajan N">N Nagarajan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Preparata, Fp" uniqKey="Preparata F">FP Preparata</name>
</author>
<author><name sortKey="Oliver, Js" uniqKey="Oliver J">JS Oliver</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Feng, S" uniqKey="Feng S">S Feng</name>
</author>
<author><name sortKey="Tillier, Erm" uniqKey="Tillier E">ERM Tillier</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chung, W H" uniqKey="Chung W">W-H Chung</name>
</author>
<author><name sortKey="Park, S B" uniqKey="Park S">S-B Park</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
<author><name sortKey="Khoshraftar, S" uniqKey="Khoshraftar S">S Khoshraftar</name>
</author>
<author><name sortKey="Mansouri Bigvand, A" uniqKey="Mansouri Bigvand A">A Mansouri Bigvand</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Mohamadi, H" uniqKey="Mohamadi H">H Mohamadi</name>
</author>
<author><name sortKey="Brian Golding, G" uniqKey="Brian Golding G">G Brian Golding</name>
</author>
<author><name sortKey="Smyth, Wf" uniqKey="Smyth W">WF Smyth</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kisman, D" uniqKey="Kisman D">D Kisman</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Li, W" uniqKey="Li W">W Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Brown, Dg" uniqKey="Brown D">DG Brown</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Roytberg, Ma" uniqKey="Roytberg M">MA Roytberg</name>
</author>
<author><name sortKey="Gambin, A" uniqKey="Gambin A">A Gambin</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Lasota, S" uniqKey="Lasota S">S Lasota</name>
</author>
<author><name sortKey="Furletova, E" uniqKey="Furletova E">E Furletova</name>
</author>
<author><name sortKey="Szczurek, E" uniqKey="Szczurek E">E Szczurek</name>
</author>
<author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Nguyen, V H" uniqKey="Nguyen V">V-H Nguyen</name>
</author>
<author><name sortKey="Lavenier, D" uniqKey="Lavenier D">D Lavenier</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Startek, M" uniqKey="Startek M">M Startek</name>
</author>
<author><name sortKey="Lasota, S" uniqKey="Lasota S">S Lasota</name>
</author>
<author><name sortKey="Sykulski, M" uniqKey="Sykulski M">M Sykulski</name>
</author>
<author><name sortKey="Bulak, A" uniqKey="Bulak A">A Bułak</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
<author><name sortKey="Gambin, A" uniqKey="Gambin A">A Gambin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, W" uniqKey="Li W">W Li</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Zhang, K" uniqKey="Zhang K">K Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Buchfink, B" uniqKey="Buchfink B">B Buchfink</name>
</author>
<author><name sortKey="Xie, C" uniqKey="Xie C">C Xie</name>
</author>
<author><name sortKey="Huson, Dh" uniqKey="Huson D">DH Huson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Somervuo, P" uniqKey="Somervuo P">P Somervuo</name>
</author>
<author><name sortKey="Holm, L" uniqKey="Holm L">L Holm</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Egidi, L" uniqKey="Egidi L">L Egidi</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Egidi, L" uniqKey="Egidi L">L Egidi</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Egidi, L" uniqKey="Egidi L">L Egidi</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Egidi, L" uniqKey="Egidi L">L Egidi</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Brejova, B" uniqKey="Brejova B">B Brejová</name>
</author>
<author><name sortKey="Brown, Dg" uniqKey="Brown D">DG Brown</name>
</author>
<author><name sortKey="Vina, T" uniqKey="Vina T">T Vinař</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Buhler, J" uniqKey="Buhler J">J Buhler</name>
</author>
<author><name sortKey="Keich, U" uniqKey="Keich U">U Keich</name>
</author>
<author><name sortKey="Sun, Y" uniqKey="Sun Y">Y Sun</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Preparata, Fp" uniqKey="Preparata F">FP Preparata</name>
</author>
<author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
<author><name sortKey="Choi, Kp" uniqKey="Choi K">KP Choi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Roytberg, Ma" uniqKey="Roytberg M">MA Roytberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kong, Y" uniqKey="Kong Y">Y Kong</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Girdea, M" uniqKey="Girdea M">M Gîrdea</name>
</author>
<author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Marschall, T" uniqKey="Marschall T">T Marschall</name>
</author>
<author><name sortKey="Herms, I" uniqKey="Herms I">I Herms</name>
</author>
<author><name sortKey="Kaltenbach, H M" uniqKey="Kaltenbach H">H-M Kaltenbach</name>
</author>
<author><name sortKey="Rahmann, S" uniqKey="Rahmann S">S Rahmann</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Martin, Dek" uniqKey="Martin D">DEK Martin</name>
</author>
<author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Horwege, S" uniqKey="Horwege S">S Horwege</name>
</author>
<author><name sortKey="Lindner, S" uniqKey="Lindner S">S Lindner</name>
</author>
<author><name sortKey="Boden, M" uniqKey="Boden M">M Boden</name>
</author>
<author><name sortKey="Hatje, K" uniqKey="Hatje K">K Hatje</name>
</author>
<author><name sortKey="Kollmar, M" uniqKey="Kollmar M">M Kollmar</name>
</author>
<author><name sortKey="Leimeister, C A" uniqKey="Leimeister C">C-A Leimeister</name>
</author>
<author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Leimeister, Ca" uniqKey="Leimeister C">CA Leimeister</name>
</author>
<author><name sortKey="Boden, M" uniqKey="Boden M">M Boden</name>
</author>
<author><name sortKey="Horwege, S" uniqKey="Horwege S">S Horwege</name>
</author>
<author><name sortKey="Lindner, S" uniqKey="Lindner S">S Lindner</name>
</author>
<author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ghandi, M" uniqKey="Ghandi M">M Ghandi</name>
</author>
<author><name sortKey="Mohammad Noori, M" uniqKey="Mohammad Noori M">M Mohammad-Noori</name>
</author>
<author><name sortKey="Beer, Ma" uniqKey="Beer M">MA Beer</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name>
</author>
<author><name sortKey="Zhu, B" uniqKey="Zhu B">B Zhu</name>
</author>
<author><name sortKey="Horwege, S" uniqKey="Horwege S">S Horwege</name>
</author>
<author><name sortKey="Leimeister, Ca" uniqKey="Leimeister C">CA Leimeister</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="B Inda, K" uniqKey="B Inda K">K Břinda</name>
</author>
<author><name sortKey="Sykulski, M" uniqKey="Sykulski M">M Sykulski</name>
</author>
<author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Gheraibia, Y" uniqKey="Gheraibia Y">Y Gheraibia</name>
</author>
<author><name sortKey="Moussaoui, A" uniqKey="Moussaoui A">A Moussaoui</name>
</author>
<author><name sortKey="Djenouri, Y" uniqKey="Djenouri Y">Y Djenouri</name>
</author>
<author><name sortKey="Kabir, S" uniqKey="Kabir S">S Kabir</name>
</author>
<author><name sortKey="Yin, P Y" uniqKey="Yin P">P-Y Yin</name>
</author>
<author><name sortKey="Mazouzi, S" uniqKey="Mazouzi S">S Mazouzi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hahn, L" uniqKey="Hahn L">L Hahn</name>
</author>
<author><name sortKey="Leimeister, C A" uniqKey="Leimeister C">C-A Leimeister</name>
</author>
<author><name sortKey="Ounit, R" uniqKey="Ounit R">R Ounit</name>
</author>
<author><name sortKey="Lonardi, S" uniqKey="Lonardi S">S Lonardi</name>
</author>
<author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Choi, Kp" uniqKey="Choi K">KP Choi</name>
</author>
<author><name sortKey="Zeng, F" uniqKey="Zeng F">F Zeng</name>
</author>
<author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Allauzen, C" uniqKey="Allauzen C">C Allauzen</name>
</author>
<author><name sortKey="Riley, M" uniqKey="Riley M">M Riley</name>
</author>
<author><name sortKey="Schalkwyk, J" uniqKey="Schalkwyk J">J Schalkwyk</name>
</author>
<author><name sortKey="Skut, W" uniqKey="Skut W">W Skut</name>
</author>
<author><name sortKey="Mohri, M" uniqKey="Mohri M">M Mohri</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Hopcroft, Je" uniqKey="Hopcroft J">JE Hopcroft</name>
</author>
<author><name sortKey="Motwani, R" uniqKey="Motwani R">R Motwani</name>
</author>
<author><name sortKey="Ullman, Jd" uniqKey="Ullman J">JD Ullman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Aston, Jad" uniqKey="Aston J">JAD Aston</name>
</author>
<author><name sortKey="Martin, Dek" uniqKey="Martin D">DEK Martin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name>
</author>
<author><name sortKey="Martin, Dek" uniqKey="Martin D">DEK Martin</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Nicodeme, P" uniqKey="Nicodeme P">P Nicodème</name>
</author>
<author><name sortKey="Salvy, B" uniqKey="Salvy B">B Salvy</name>
</author>
<author><name sortKey="Flajolet, P" uniqKey="Flajolet P">P Flajolet</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">Algorithms Mol Biol</journal-id>
<journal-id journal-id-type="iso-abbrev">Algorithms Mol Biol</journal-id>
<journal-title-group><journal-title>Algorithms for Molecular Biology : AMB</journal-title>
</journal-title-group>
<issn pub-type="epub">1748-7188</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
<publisher-loc>London</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">28289437</article-id>
<article-id pub-id-type="pmc">5310094</article-id>
<article-id pub-id-type="publisher-id">92</article-id>
<article-id pub-id-type="doi">10.1186/s13015-017-0092-1</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research</subject>
</subj-group>
</article-categories>
<title-group><article-title>Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">http://orcid.org/0000-0002-1170-8376</contrib-id>
<name><surname>Noé</surname>
<given-names>Laurent</given-names>
</name>
<address><email>laurent.noe@univ-lille.fr</email>
</address>
<xref ref-type="aff" rid="Aff1"></xref>
</contrib>
<aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2186 1211</institution-id>
<institution-id institution-id-type="GRID">grid.4461.7</institution-id>
<institution>CRIStAL (UMR 9189 Lille University/CNRS)-Inria Lille, Bat M3 ext,</institution>
<institution>Université Lille 1,</institution>
</institution-wrap>
59655 Villeneuve d’Ascq, France</aff>
</contrib-group>
<pub-date pub-type="epub"><day>14</day>
<month>2</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>14</day>
<month>2</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="collection"><year>2017</year>
</pub-date>
<volume>12</volume>
<elocation-id>1</elocation-id>
<history><date date-type="received"><day>19</day>
<month>9</month>
<year>2016</year>
</date>
<date date-type="accepted"><day>30</day>
<month>1</month>
<year>2017</year>
</date>
</history>
<permissions><copyright-statement>© The Author(s) 2017</copyright-statement>
<license license-type="OpenAccess"><license-p><bold>Open Access</bold>
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>
) applies to the data made available in this article, unless otherwise stated.</license-p>
</license>
</permissions>
<abstract id="Abs1"><sec><title>Background</title>
<p><italic>Spaced seeds</italic>
, also named <italic>gapped q-grams, gapped k-mers, spaced q-grams</italic>
, have been proven to be more sensitive than contiguous seeds (<italic>contiguous q-grams, contiguous k-mers</italic>
) in nucleic and amino-acid sequences analysis. Initially proposed to detect sequence similarities and to anchor sequence alignments, spaced seeds have more recently been applied in several <italic>alignment-free</italic>
related methods. Unfortunately, spaced seeds need to be initially designed. This task is known to be time-consuming due to the number of spaced seed candidates. Moreover, it can be altered by a set of <italic>arbitrary chosen</italic>
parameters from the probabilistic alignment models used. In this general context, <italic>Dominant seeds</italic>
have been introduced by Mak and Benson (Bioinformatics 25:302–308, 2009) on the Bernoulli model, in order to reduce the number of spaced seed candidates that are further processed in a <italic>parameter-free</italic>
calculation of the sensitivity.</p>
</sec>
<sec><title>Results</title>
<p>We expand the scope of work of Mak and Benson on single and multiple seeds by considering the Hit Integration model of Chung and Park (BMC Bioinform 11:31, 2010), demonstrate that the same dominance definition can be applied, and that a parameter-free study can be performed without any significant additional cost. We also consider two new discrete models, namely the Heaviside and the Dirac models, where lossless seeds can be integrated. From a theoretical standpoint, we establish a generic framework on all the proposed models, by applying a <italic>counting semi-ring</italic>
to quickly compute large polynomial coefficients needed by the <italic>dominance</italic>
filter. From a practical standpoint, we confirm that <italic>dominant seeds</italic>
reduce the set of, either single seeds to thoroughly analyse, or multiple seeds to store. Moreover, in <ext-link ext-link-type="uri" xlink:href="http://bioinfo.cristal.univ-lille.fr/yass/iedera%5fdominance">http://bioinfo.cristal.univ-lille.fr/yass/iedera_dominance</ext-link>
, we provide a full list of spaced seeds computed on the four aforementioned models, with one (continuous) parameter left free for each model, and with several (discrete) alignment lengths.</p>
</sec>
</abstract>
<kwd-group xml:lang="en"><title>Keywords</title>
<kwd>Spaced seeds</kwd>
<kwd>Dominant seeds</kwd>
<kwd>Bernoulli</kwd>
<kwd>Hit Integration</kwd>
<kwd>Heaviside</kwd>
<kwd>Dirac</kwd>
<kwd>Counting semi-ring</kwd>
<kwd>Polynomial form</kwd>
<kwd>DFA</kwd>
</kwd-group>
<funding-group><award-group><funding-source><institution>INRIA</institution>
</funding-source>
</award-group>
</funding-group>
<custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name>
<meta-value>© The Author(s) 2017</meta-value>
</custom-meta>
</custom-meta-group>
</article-meta>
</front>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000246 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd -nk 000246 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Curation |type= RBID |clé= PMC:5310094 |texte= Best hits of 11110110111: model-free selection and parameter-free sensitivity calculation of spaced seeds }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Curation/RBID.i -Sk "pubmed:28289437" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |