Efficient sequential and parallel algorithms for finding edit distance based motifs
Identifieur interne : 001756 ( Ncbi/Merge ); précédent : 001755; suivant : 001757Efficient 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
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
Links to Exploration step
PMC:5001234Le 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></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><double pmid="27557423"><pmc><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></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></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></pmc><pubmed><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="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author><author><name sortKey="Xiao, Peng" sort="Xiao, Peng" uniqKey="Xiao P" first="Peng" last="Xiao">Peng Xiao</name><affiliation wicri:level="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author><author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name><affiliation wicri:level="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA. rajasek@engr.uconn.edu.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2016">2016</date><idno type="RBID">pubmed:27557423</idno><idno type="pmid">27557423</idno><idno type="doi">10.1186/s12864-016-2789-9</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></publicationStmt><sourceDesc><biblStruct><analytic><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="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author><author><name sortKey="Xiao, Peng" sort="Xiao, Peng" uniqKey="Xiao P" first="Peng" last="Xiao">Peng Xiao</name><affiliation wicri:level="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author><author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name><affiliation wicri:level="2"><nlm:affiliation>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT, USA. rajasek@engr.uconn.edu.</nlm:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Road,, Storrs, 06269, CT</wicri:regionArea><placeName><region type="state">Connecticut</region></placeName></affiliation></author></analytic><series><title level="j">BMC genomics</title><idno type="eISSN">1471-2164</idno><imprint><date when="2016" type="published">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">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 (l,d) Edit-distance-based Motif Search (EMS) problem: given two integers l,d and n biological strings, find all strings of length l that appear in each input string with atmost d errors of types substitution, insertion and deletion.</div></front></TEI></pubmed></double></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001756 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 001756 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Ncbi
|étape= Merge
|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/Ncbi/Merge/RBID.i -Sk "pubmed:27557423" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |