Efficient sequential and parallel algorithms for finding edit distance based motifs
Identifieur interne : 001286 ( Main/Exploration ); précédent : 001285; suivant : 001287Efficient sequential and parallel algorithms for finding edit distance based motifs
Auteurs : Soumitra Pal [États-Unis] ; Peng Xiao [États-Unis] ; Sanguthevar Rajasekaran [États-Unis]Source :
- BMC Genomics [ 1471-2164 ] ; 2016.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- genetics : Amino Acid Motifs, Nucleotide Motifs.
- methods : Computational Biology, Sequence Analysis, DNA, Sequence Analysis, Protein.
- Algorithms, Software.
Abstract
Motif search is an important step in extracting meaningful patterns from biological data. The general problem of motif search is intractable and there is a pressing need to develop efficient, exact and approximation algorithms to solve this problem. In this paper, we present several novel, exact, sequential and parallel algorithms for solving the (
One popular technique to solve the problem is to explore for each input string the set of all possible
The algorithms for EMS are customarily evaluated on several challenging instances such as (8,1), (12,2), (16,3), (20,4), and so on. The best previously known algorithm, EMS1, is sequential and in estimated 3 days solves up to instance (16,3). Our sequential algorithms are more than 20 times faster on (16,3). On other hard instances such as (9,2), (11,3), (13,4), our algorithms are much faster. Our parallel algorithm has more than 600 % scaling performance while using 16 threads.
Our algorithms have pushed up the state-of-the-art of EMS solvers and we believe that the techniques introduced in this paper are also applicable to other motif search problems such as Planted Motif Search (PMS) and Simple Motif Search (SMS).
The online version of this article (doi:10.1186/s12864-016-2789-9) contains supplementary material, which is available to authorized users.
Url:
DOI: 10.1186/s12864-016-2789-9
PubMed: 27557423
PubMed Central: 5001234
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000294
- to stream Pmc, to step Curation: 000294
- to stream Pmc, to step Checkpoint: 000B88
- to stream PubMed, to step Corpus: 000F92
- to stream PubMed, to step Curation: 000F92
- to stream PubMed, to step Checkpoint: 001132
- to stream Ncbi, to step Merge: 001756
- to stream Ncbi, to step Curation: 001756
- to stream Ncbi, to step Checkpoint: 001756
- to stream Main, to step Merge: 001290
- to stream Main, to step Curation: 001286
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient sequential and parallel algorithms for finding edit distance based motifs</title>
<author><name sortKey="Pal, Soumitra" sort="Pal, Soumitra" uniqKey="Pal S" first="Soumitra" last="Pal">Soumitra Pal</name>
<affiliation wicri:level="1"><nlm:aff id="Aff1">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Xiao, Peng" sort="Xiao, Peng" uniqKey="Xiao P" first="Peng" last="Xiao">Peng Xiao</name>
<affiliation wicri:level="1"><nlm:aff id="Aff1">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</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="Aff2">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">27557423</idno>
<idno type="pmc">5001234</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5001234</idno>
<idno type="RBID">PMC:5001234</idno>
<idno type="doi">10.1186/s12864-016-2789-9</idno>
<date when="2016">2016</date>
<idno type="wicri:Area/Pmc/Corpus">000294</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000294</idno>
<idno type="wicri:Area/Pmc/Curation">000294</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000294</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000B88</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000B88</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="RBID">pubmed:27557423</idno>
<idno type="wicri:Area/PubMed/Corpus">000F92</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000F92</idno>
<idno type="wicri:Area/PubMed/Curation">000F92</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000F92</idno>
<idno type="wicri:Area/PubMed/Checkpoint">001132</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">001132</idno>
<idno type="wicri:Area/Ncbi/Merge">001756</idno>
<idno type="wicri:Area/Ncbi/Curation">001756</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">001756</idno>
<idno type="wicri:Area/Main/Merge">001290</idno>
<idno type="wicri:Area/Main/Curation">001286</idno>
<idno type="wicri:Area/Main/Exploration">001286</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Efficient sequential and parallel algorithms for finding edit distance based motifs</title>
<author><name sortKey="Pal, Soumitra" sort="Pal, Soumitra" uniqKey="Pal S" first="Soumitra" last="Pal">Soumitra Pal</name>
<affiliation wicri:level="1"><nlm:aff id="Aff1">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Xiao, Peng" sort="Xiao, Peng" uniqKey="Xiao P" first="Peng" last="Xiao">Peng Xiao</name>
<affiliation wicri:level="1"><nlm:aff id="Aff1">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</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="Aff2">Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269 CT USA</nlm:aff>
<country>États-Unis</country>
<placeName><region type="state">Connecticut</region>
</placeName>
<wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs</wicri:regionArea>
<wicri:noRegion>Storrs</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Genomics</title>
<idno type="eISSN">1471-2164</idno>
<imprint><date when="2016">2016</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Amino Acid Motifs (genetics)</term>
<term>Computational Biology (methods)</term>
<term>Nucleotide Motifs (genetics)</term>
<term>Sequence Analysis, DNA (methods)</term>
<term>Sequence Analysis, Protein (methods)</term>
<term>Software</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence d'ADN ()</term>
<term>Analyse de séquence de protéine ()</term>
<term>Biologie informatique ()</term>
<term>Logiciel</term>
<term>Motifs d'acides aminés (génétique)</term>
<term>Motifs nucléotidiques (génétique)</term>
</keywords>
<keywords scheme="MESH" qualifier="genetics" xml:lang="en"><term>Amino Acid Motifs</term>
<term>Nucleotide Motifs</term>
</keywords>
<keywords scheme="MESH" qualifier="génétique" xml:lang="fr"><term>Motifs d'acides aminés</term>
<term>Motifs nucléotidiques</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
<term>Sequence Analysis, DNA</term>
<term>Sequence Analysis, Protein</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Analyse de séquence d'ADN</term>
<term>Analyse de séquence de protéine</term>
<term>Biologie informatique</term>
<term>Logiciel</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>Motif search is an important step in extracting meaningful patterns from biological data. The general problem of motif search is intractable and there is a pressing need to develop efficient, exact and approximation algorithms to solve this problem. In this paper, we present several novel, exact, sequential and parallel algorithms for solving the (<italic>l,d</italic>
) <italic>Edit-distance-based Motif Search (EMS)</italic>
problem: given two integers <italic>l,d</italic>
and <italic>n</italic>
biological strings, find all strings of length <italic>l</italic>
that appear in each input string with atmost <italic>d</italic>
errors of types substitution, insertion and deletion.</p>
</sec>
<sec><title>Methods</title>
<p>One popular technique to solve the problem is to explore for each input string the set of all possible <italic>l</italic>
-mers that belong to the <italic>d</italic>
-neighborhood of any substring of the input string and output those which are common for all input strings. We introduce a novel and provably efficient neighborhood exploration technique. We show that it is enough to consider the candidates in neighborhood which are at a distance exactly <italic>d</italic>
. We compactly represent these candidate motifs using wildcard characters and efficiently explore them with very few repetitions. Our sequential algorithm uses a trie based data structure to efficiently store and sort the candidate motifs. Our parallel algorithm in a multi-core shared memory setting uses arrays for storing and a novel modification of radix-sort for sorting the candidate motifs.</p>
</sec>
<sec><title>Results</title>
<p>The algorithms for EMS are customarily evaluated on several challenging instances such as (8,1), (12,2), (16,3), (20,4), and so on. The best previously known algorithm, EMS1, is sequential and in estimated 3 days solves up to instance (16,3). Our sequential algorithms are more than 20 times faster on (16,3). On other hard instances such as (9,2), (11,3), (13,4), our algorithms are much faster. Our parallel algorithm has more than 600 % scaling performance while using 16 threads.</p>
</sec>
<sec><title>Conclusions</title>
<p>Our algorithms have pushed up the state-of-the-art of EMS solvers and we believe that the techniques introduced in this paper are also applicable to other motif search problems such as Planted Motif Search (PMS) and Simple Motif Search (SMS).</p>
</sec>
<sec><title>Electronic supplementary material</title>
<p>The online version of this article (doi:10.1186/s12864-016-2789-9) contains supplementary material, which is available to authorized users.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Nicolae, M" uniqKey="Nicolae M">M Nicolae</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tanaka, S" uniqKey="Tanaka S">S Tanaka</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="Karlin, S" uniqKey="Karlin S">S Karlin</name>
</author>
<author><name sortKey="Ost, F" uniqKey="Ost F">F Ost</name>
</author>
<author><name sortKey="Blaisdell, Be" uniqKey="Blaisdell B">BE Blaisdell</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rocke, E" uniqKey="Rocke E">E Rocke</name>
</author>
<author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sagot, Mf" uniqKey="Sagot M">MF Sagot</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lanctot, Jk" uniqKey="Lanctot J">JK 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="Adebiyi, Ef" uniqKey="Adebiyi E">EF Adebiyi</name>
</author>
<author><name sortKey="Kaufmann, M" uniqKey="Kaufmann M">M Kaufmann</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wang, X" uniqKey="Wang X">X Wang</name>
</author>
<author><name sortKey="Miao, Y" uniqKey="Miao Y">Y Miao</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
<author><name sortKey="Balla, S" uniqKey="Balla S">S Balla</name>
</author>
<author><name sortKey="Huang, Ch" uniqKey="Huang C">CH Huang</name>
</author>
<author><name sortKey="Thapar, V" uniqKey="Thapar V">V Thapar</name>
</author>
<author><name sortKey="Gryk, M" uniqKey="Gryk M">M Gryk</name>
</author>
<author><name sortKey="Maciejewski, M" uniqKey="Maciejewski M">M Maciejewski</name>
</author>
<author><name sortKey="Schiller, M" uniqKey="Schiller M">M Schiller</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pathak, S" uniqKey="Pathak S">S Pathak</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
<author><name sortKey="Nicolae, M" uniqKey="Nicolae M">M Nicolae</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Knuth, De" uniqKey="Knuth D">DE Knuth</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Connecticut</li>
</region>
</list>
<tree><country name="États-Unis"><region name="Connecticut"><name sortKey="Pal, Soumitra" sort="Pal, Soumitra" uniqKey="Pal S" first="Soumitra" last="Pal">Soumitra Pal</name>
</region>
<name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name>
<name sortKey="Xiao, Peng" sort="Xiao, Peng" uniqKey="Xiao P" first="Peng" last="Xiao">Peng Xiao</name>
</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 001286 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001286 | 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:5001234 |texte= Efficient sequential and parallel algorithms for finding edit distance based motifs }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:27557423" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |