Efficient sequential and parallel algorithms for planted motif search
Identifieur interne : 000950 ( Pmc/Curation ); précédent : 000949; suivant : 000951Efficient sequential and parallel algorithms for planted motif search
Auteurs : Marius Nicolae [États-Unis] ; Sanguthevar Rajasekaran [États-Unis]Source :
- BMC Bioinformatics [ 1471-2105 ] ; 2014.
Abstract
Motif searching is an important step in the detection of rare events occurring in a set of DNA or protein sequences. One formulation of the problem is known as (
This paper presents a fast exact parallel PMS algorithm called PMS8. PMS8 is the first algorithm to solve the challenging (
We present PMS8, an efficient exact algorithm for Planted Motif Search. PMS8 introduces novel ideas for generating common neighborhoods. We have also implemented a parallel version for this algorithm. PMS8 can solve instances not solved by any previous algorithms.
Url:
DOI: 10.1186/1471-2105-15-34
PubMed: 24479443
PubMed Central: 3924400
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000950
Links to Exploration step
PMC:3924400Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient sequential and parallel algorithms for planted motif search</title>
<author><name sortKey="Nicolae, Marius" sort="Nicolae, Marius" uniqKey="Nicolae M" first="Marius" last="Nicolae">Marius Nicolae</name>
<affiliation wicri:level="1"><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, Storrs, CT</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name>
<affiliation wicri:level="1"><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, Storrs, CT</wicri:regionArea>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">24479443</idno>
<idno type="pmc">3924400</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3924400</idno>
<idno type="RBID">PMC:3924400</idno>
<idno type="doi">10.1186/1471-2105-15-34</idno>
<date when="2014">2014</date>
<idno type="wicri:Area/Pmc/Corpus">000950</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000950</idno>
<idno type="wicri:Area/Pmc/Curation">000950</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000950</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Efficient sequential and parallel algorithms for planted motif search</title>
<author><name sortKey="Nicolae, Marius" sort="Nicolae, Marius" uniqKey="Nicolae M" first="Marius" last="Nicolae">Marius Nicolae</name>
<affiliation wicri:level="1"><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, Storrs, CT</wicri:regionArea>
</affiliation>
</author>
<author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name>
<affiliation wicri:level="1"><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, Storrs, CT</wicri:regionArea>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2014">2014</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>Motif searching is an important step in the detection of rare events occurring in a set of DNA or protein sequences. One formulation of the problem is known as (<italic>l</italic>
,<italic>d</italic>
)-motif search or Planted Motif Search (PMS). In PMS we are given two integers <italic>l</italic>
and <italic>d</italic>
and <italic>n</italic>
biological sequences. We want to find all sequences of length <italic>l</italic>
that appear in each of the input sequences with at most <italic>d</italic>
mismatches. The PMS problem is NP-complete. PMS algorithms are typically evaluated on certain instances considered challenging. Despite ample research in the area, a considerable performance gap exists because many state of the art algorithms have large runtimes even for moderately challenging instances.</p>
</sec>
<sec><title>Results</title>
<p>This paper presents a fast exact parallel PMS algorithm called PMS8. PMS8 is the first algorithm to solve the challenging (<italic>l</italic>
,<italic>d</italic>
) instances (25,10) and (26,11). PMS8 is also efficient on instances with larger <italic>l</italic>
and <italic>d</italic>
such as (50,21). We include a comparison of PMS8 with several state of the art algorithms on multiple problem instances. This paper also presents necessary and sufficient conditions for 3 <italic>l</italic>
-mers to have a common <italic>d</italic>
-neighbor. The program is freely available at <ext-link ext-link-type="uri" xlink:href="http://engr.uconn.edu/~man09004/PMS8/">http://engr.uconn.edu/~man09004/PMS8/</ext-link>
.</p>
</sec>
<sec><title>Conclusions</title>
<p>We present PMS8, an efficient exact algorithm for Planted Motif Search. PMS8 introduces novel ideas for generating common neighborhoods. We have also implemented a parallel version for this algorithm. PMS8 can solve instances not solved by any previous algorithms.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Pevzner, P" uniqKey="Pevzner P">P Pevzner</name>
</author>
<author><name sortKey="Sze, S" uniqKey="Sze S">S Sze</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lanctot, J" uniqKey="Lanctot J">J Lanctot</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="Wang, S" uniqKey="Wang S">S Wang</name>
</author>
<author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Q" uniqKey="Yu Q">Q Yu</name>
</author>
<author><name sortKey="Huo, H" uniqKey="Huo H">H Huo</name>
</author>
<author><name sortKey="Zhang, Y" uniqKey="Zhang Y">Y Zhang</name>
</author>
<author><name sortKey="Guo, H" uniqKey="Guo H">H Guo</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Davila, J" uniqKey="Davila J">J Davila</name>
</author>
<author><name sortKey="Balla, S" uniqKey="Balla S">S Balla</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dinh, H" uniqKey="Dinh H">H Dinh</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
<author><name sortKey="Davila, J" uniqKey="Davila J">J Davila</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ho, E" uniqKey="Ho E">E Ho</name>
</author>
<author><name sortKey="Jakubowski, C" uniqKey="Jakubowski C">C Jakubowski</name>
</author>
<author><name sortKey="Gunderson, S" uniqKey="Gunderson S">S Gunderson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Desaraju, S" uniqKey="Desaraju S">S Desaraju</name>
</author>
<author><name sortKey="Mukkamala, R" uniqKey="Mukkamala R">R Mukkamala</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dinh, H" uniqKey="Dinh H">H Dinh</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
<author><name sortKey="Kundeti, V" uniqKey="Kundeti V">V Kundeti</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bandyopadhyay, S" uniqKey="Bandyopadhyay S">S Bandyopadhyay</name>
</author>
<author><name sortKey="Sahni, S" uniqKey="Sahni S">S Sahni</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
<author><name sortKey="Dinh, H" uniqKey="Dinh H">H Dinh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gramm, J" uniqKey="Gramm J">J Gramm</name>
</author>
<author><name sortKey="Niedermeier, R" uniqKey="Niedermeier R">R Niedermeier</name>
</author>
<author><name sortKey="Rossmanith, P" uniqKey="Rossmanith P">P Rossmanith</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Abbas, M" uniqKey="Abbas M">M Abbas</name>
</author>
<author><name sortKey="Abouelhoda, M" uniqKey="Abouelhoda M">M Abouelhoda</name>
</author>
<author><name sortKey="Bahig, H" uniqKey="Bahig H">H Bahig</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dasari, N" uniqKey="Dasari N">N Dasari</name>
</author>
<author><name sortKey="Ranjan, D" uniqKey="Ranjan D">D Ranjan</name>
</author>
<author><name sortKey="Zubair, M" uniqKey="Zubair M">M Zubair</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dasari, N" uniqKey="Dasari N">N Dasari</name>
</author>
<author><name sortKey="Desh, R" uniqKey="Desh R">R Desh</name>
</author>
<author><name sortKey="Zubair, M" uniqKey="Zubair M">M Zubair</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dasari, Ns" uniqKey="Dasari N">NS Dasari</name>
</author>
<author><name sortKey="Desh, R" uniqKey="Desh R">R Desh</name>
</author>
<author><name sortKey="Zubair, M" uniqKey="Zubair M">M Zubair</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sahoo, B" uniqKey="Sahoo B">B Sahoo</name>
</author>
<author><name sortKey="Sourav, R" uniqKey="Sourav R">R Sourav</name>
</author>
<author><name sortKey="Ranjan, R" uniqKey="Ranjan R">R Ranjan</name>
</author>
<author><name sortKey="Padhy, S" uniqKey="Padhy S">S Padhy</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sun, H" uniqKey="Sun H">H Sun</name>
</author>
<author><name sortKey="Low, M" uniqKey="Low M">M Low</name>
</author>
<author><name sortKey="Hsu, W" uniqKey="Hsu W">W Hsu</name>
</author>
<author><name sortKey="Tan, C" uniqKey="Tan C">C Tan</name>
</author>
<author><name sortKey="Rajapakse, J" uniqKey="Rajapakse J">J Rajapakse</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sun, Hq" uniqKey="Sun H">HQ Sun</name>
</author>
<author><name sortKey="Low, M" uniqKey="Low M">M Low</name>
</author>
<author><name sortKey="Hsu, Wj" uniqKey="Hsu W">WJ Hsu</name>
</author>
<author><name sortKey="Rajapakse, J" uniqKey="Rajapakse J">J Rajapakse</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Faheem, Hm" uniqKey="Faheem H">HM Faheem</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
<author><name sortKey="Li, N" uniqKey="Li N">N Li</name>
</author>
<author><name sortKey="Bailey, Tl" uniqKey="Bailey T">TL Bailey</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
<author><name sortKey="De Moor, B" uniqKey="De Moor B">B De Moor</name>
</author>
<author><name sortKey="Eskin, E" uniqKey="Eskin E">E Eskin</name>
</author>
<author><name sortKey="Favorov, Av" uniqKey="Favorov A">AV Favorov</name>
</author>
<author><name sortKey="Frith, Mc" uniqKey="Frith M">MC Frith</name>
</author>
<author><name sortKey="Fu, Y" uniqKey="Fu Y">Y Fu</name>
</author>
<author><name sortKey="Kent, Wj" uniqKey="Kent W">WJ Kent</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article" xml:lang="en"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Bioinformatics</journal-id>
<journal-id journal-id-type="iso-abbrev">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">24479443</article-id>
<article-id pub-id-type="pmc">3924400</article-id>
<article-id pub-id-type="publisher-id">1471-2105-15-34</article-id>
<article-id pub-id-type="doi">10.1186/1471-2105-15-34</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject>
</subj-group>
</article-categories>
<title-group><article-title>Efficient sequential and parallel algorithms for planted motif search</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" corresp="yes" id="A1"><name><surname>Nicolae</surname>
<given-names>Marius</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>marius.nicolae@engr.uconn.edu</email>
</contrib>
<contrib contrib-type="author" id="A2"><name><surname>Rajasekaran</surname>
<given-names>Sanguthevar</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>rajasek@engr.uconn.edu</email>
</contrib>
</contrib-group>
<aff id="I1"><label>1</label>
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</aff>
<pub-date pub-type="collection"><year>2014</year>
</pub-date>
<pub-date pub-type="epub"><day>31</day>
<month>1</month>
<year>2014</year>
</pub-date>
<volume>15</volume>
<fpage>34</fpage>
<lpage>34</lpage>
<history><date date-type="received"><day>15</day>
<month>3</month>
<year>2013</year>
</date>
<date date-type="accepted"><day>27</day>
<month>1</month>
<year>2014</year>
</date>
</history>
<permissions><copyright-statement>Copyright © 2014 Nicolae and Rajasekaran; licensee BioMed Central Ltd.</copyright-statement>
<copyright-year>2014</copyright-year>
<copyright-holder>Nicolae and Rajasekaran; licensee BioMed Central Ltd.</copyright-holder>
<license license-type="open-access" xlink:href="http://creativecommons.org/licenses/by/2.0"><license-p>This is an Open Access article distributed under the terms of the Creative Commons Attribution License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/2.0">http://creativecommons.org/licenses/by/2.0</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</license-p>
</license>
</permissions>
<self-uri xlink:href="http://www.biomedcentral.com/1471-2105/15/34"></self-uri>
<abstract><sec><title>Background</title>
<p>Motif searching is an important step in the detection of rare events occurring in a set of DNA or protein sequences. One formulation of the problem is known as (<italic>l</italic>
,<italic>d</italic>
)-motif search or Planted Motif Search (PMS). In PMS we are given two integers <italic>l</italic>
and <italic>d</italic>
and <italic>n</italic>
biological sequences. We want to find all sequences of length <italic>l</italic>
that appear in each of the input sequences with at most <italic>d</italic>
mismatches. The PMS problem is NP-complete. PMS algorithms are typically evaluated on certain instances considered challenging. Despite ample research in the area, a considerable performance gap exists because many state of the art algorithms have large runtimes even for moderately challenging instances.</p>
</sec>
<sec><title>Results</title>
<p>This paper presents a fast exact parallel PMS algorithm called PMS8. PMS8 is the first algorithm to solve the challenging (<italic>l</italic>
,<italic>d</italic>
) instances (25,10) and (26,11). PMS8 is also efficient on instances with larger <italic>l</italic>
and <italic>d</italic>
such as (50,21). We include a comparison of PMS8 with several state of the art algorithms on multiple problem instances. This paper also presents necessary and sufficient conditions for 3 <italic>l</italic>
-mers to have a common <italic>d</italic>
-neighbor. The program is freely available at <ext-link ext-link-type="uri" xlink:href="http://engr.uconn.edu/~man09004/PMS8/">http://engr.uconn.edu/~man09004/PMS8/</ext-link>
.</p>
</sec>
<sec><title>Conclusions</title>
<p>We present PMS8, an efficient exact algorithm for Planted Motif Search. PMS8 introduces novel ideas for generating common neighborhoods. We have also implemented a parallel version for this algorithm. PMS8 can solve instances not solved by any previous algorithms.</p>
</sec>
</abstract>
</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 000950 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd -nk 000950 | 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:3924400 |texte= Efficient sequential and parallel algorithms for planted motif search }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Curation/RBID.i -Sk "pubmed:24479443" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |