Links to Exploration step
Le 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><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name>
<affiliation><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
</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>
</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><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Rajasekaran, Sanguthevar" sort="Rajasekaran, Sanguthevar" uniqKey="Rajasekaran S" first="Sanguthevar" last="Rajasekaran">Sanguthevar Rajasekaran</name>
<affiliation><nlm:aff id="I1">Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA</nlm:aff>
</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>
<body><sec><title>Background</title>
<p>This paper presents an efficient exact parallel algorithm for the Planted Motif Search (PMS) problem also known as the (<italic>l</italic>
,<italic>d</italic>
) motif problem [<xref ref-type="bibr" rid="B1">1</xref>
]. A string of length <italic>l</italic>
is caller an <italic>l</italic>
-mer. The number of positions where two <italic>l</italic>
-mers <italic>u</italic>
and <italic>v</italic>
differ is called their Hamming distance and is denoted by <italic>H</italic>
<italic>d</italic>
(<italic>u</italic>
,<italic>v</italic>
). For any string <italic>T</italic>
, <italic>T</italic>
[ <italic>i</italic>
..<italic>j</italic>
] is the substring of <italic>T</italic>
starting at position <italic>i</italic>
and ending at position <italic>j</italic>
. The PMS problem is the following. Given <italic>n</italic>
sequences <italic>S</italic>
<sub>1</sub>
,<italic>S</italic>
<sub>2</sub>
,…,<italic>S</italic>
<sub><italic>n</italic>
</sub>
of length <italic>m</italic>
each, from an alphabet <italic>Σ</italic>
and two integers <italic>l</italic>
and <italic>d</italic>
, identify all <italic>l</italic>
-mers <italic>M</italic>
,<italic>M</italic>
∈<italic>Σ</italic>
<sup><italic>l</italic>
</sup>
, that occur in at least one location in each of the <italic>n</italic>
sequences with a Hamming distance of at most <italic>d</italic>
. More formally, <italic>M</italic>
is a motif if and only if ∀<italic>i</italic>
,1≤<italic>i</italic>
≤<italic>n</italic>
,∃<italic>j</italic>
<sub><italic>i</italic>
</sub>
,1≤<italic>j</italic>
<sub><italic>i</italic>
</sub>
≤<italic>m</italic>
-<italic>l</italic>
+1, such that <italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>S</italic>
<sub><italic>i</italic>
</sub>
[<italic>j</italic>
<sub><italic>i</italic>
</sub>
..<italic>j</italic>
<sub><italic>i</italic>
</sub>
+<italic>m</italic>
-1])≤<italic>d</italic>
.</p>
<p>The PMS problem is essentially the same as the Closest Substring problem. These problems have applications in PCR primer design, genetic probe design, discovering potential drug targets, antisense drug design, finding unbiased consensus of a protein family, creating diagnostic probes and motif finding (see e.g., [<xref ref-type="bibr" rid="B2">2</xref>
]). Therefore, efficient algorithms for solving the PMS problem are very important in biology and bioinformatics.</p>
<p>A PMS algorithm that finds all the motifs for a given input is called an exact algorithm. All known exact algorithms have an exponential worst case runtime because the PMS problem is NP-complete [<xref ref-type="bibr" rid="B2">2</xref>
]. An exact algorithm can be built using two approaches. One is sample driven: for all (<italic>m</italic>
-<italic>l</italic>
+1)<sup><italic>n</italic>
</sup>
possible combinations of <italic>l</italic>
-mers coming from different strings, generate the common neighborhood. The other is pattern-driven: for all <italic>Σ</italic>
<sup><italic>l</italic>
</sup>
possible <italic>l</italic>
-mers check which are motifs. Many algorithms employ a combination of these two techniques. For example, [<xref ref-type="bibr" rid="B3">3</xref>
] and [<xref ref-type="bibr" rid="B4">4</xref>
] generate the common neighbors for every pair of <italic>l</italic>
-mers coming from two of the input strings. Every neighbor is then matched against the remaining <italic>n</italic>
-2 input strings to confirm or reject it as a motif. Other algorithms ([<xref ref-type="bibr" rid="B5">5</xref>
,<xref ref-type="bibr" rid="B6">6</xref>
]) consider groups of three <italic>l</italic>
-mers instead of two.</p>
<p>PMS algorithms are typically tested on instances generated as follows (also see [<xref ref-type="bibr" rid="B1">1</xref>
,<xref ref-type="bibr" rid="B4">4</xref>
]): 20 DNA strings of length 600 are generated according to the i.i.d. (independent identically distributed) model. A random <italic>l</italic>
-mer is chosen as a motif and planted at a random location in each input string. Every planted instance is modified in at most <italic>d</italic>
positions. For a given integer <italic>l</italic>
, the instance (<italic>l</italic>
,<italic>d</italic>
) is defined to be challenging if <italic>d</italic>
is the smallest integer for which the expected number of motifs of length <italic>l</italic>
that occur in the input by random chance is ≥1. Some of the challenging instances are (13,4),(15,5),(17,6),(19,7),(21,8),(23,9),(25,10), (26,11), etc.</p>
<p>The largest challenging instance solved up to now has been (23,9). To the best of our knowledge the only algorithm to solve (23,9) has been qPMS7 [<xref ref-type="bibr" rid="B5">5</xref>
]. The algorithm in [<xref ref-type="bibr" rid="B7">7</xref>
] can solve instances with relatively large <italic>l</italic>
(up to 48) provided that <italic>d</italic>
is at most <italic>l</italic>
/4. However, most of the well known challenging instances have <italic>d</italic>
><italic>l</italic>
/4. PairMotif [<xref ref-type="bibr" rid="B3">3</xref>
] can solve instances with larger <italic>l</italic>
, such as (27,9) or (30,9), but these are significantly less challenging than (23,9). Furthermore, for instances that current algorithms have been able to solve, the runtimes are often quite large.</p>
<p>In this paper we propose a new exact algorithm, PMS8, which can efficiently solve both instances with large <italic>l</italic>
and instances with large <italic>d</italic>
. The efficiency of PMS8 comes mainly from reducing the search space by using the pruning conditions presented later in the paper, but also from a careful implementation which utilizes several speedup techniques and emphasizes cache locality.</p>
<p>One of the basic steps employed in many PMS algorithms (such as PMSprune [<xref ref-type="bibr" rid="B4">4</xref>
], PMS5 [<xref ref-type="bibr" rid="B8">8</xref>
], PMS6 [<xref ref-type="bibr" rid="B9">9</xref>
], and qPMS7 [<xref ref-type="bibr" rid="B5">5</xref>
]) is that of computing all the common neighbors of three <italic>l</italic>
-mers. In qPMS7, this problem is solved using an Integer Linear Programming (ILP) formulation. In particular, a large number of ILP instances are solved as a part of a preprocessing step and a table is populated. This table is then repeatedly looked up to identify common neighbors of three <italic>l</italic>
-mers. This preprocessing step takes a considerable amount of time and the lookup table calls for a large amount of memory. In this paper we offer a novel algorithm for computing all the common neighbors of three <italic>l</italic>
-mers. This algorithm eliminates the preprocessing step. In particular, we don’t solve any ILP instance. We also don’t employ any lookup tables and hence we reduce the memory usage. We feel that this algorithm will find independent applications. Specifically, we state and prove necessary and sufficient conditions for 3 <italic>l</italic>
-mers to have a common neighbor.</p>
</sec>
<sec sec-type="methods"><title>Methods</title>
<p>For any <italic>l</italic>
-mer <italic>u</italic>
we define its <italic>d</italic>
-neighborhood as the set of <italic>l</italic>
-mers <italic>v</italic>
for which <italic>H</italic>
<italic>d</italic>
(<italic>u</italic>
,<italic>v</italic>
)≤<italic>d</italic>
. For any set of <italic>l</italic>
-mers <italic>T</italic>
we define the common <italic>d</italic>
-neighborhood of <italic>T</italic>
as the intersection of the <italic>d</italic>
-neighborhoods of all <italic>l</italic>
-mers in <italic>T</italic>
. To compute common neighborhoods, a natural approach is to traverse the tree of all possible <italic>l</italic>
-mers and identify the common neighbors. A pseudocode is given in Appendix 1. A node at depth <italic>k</italic>
, which represents a <italic>k</italic>
-mer, is not explored deeper if certain pruning conditions are met. Thus, the better the pruning conditions are, the faster will be the algorithm. We discuss pruning conditions in a later section.</p>
<p>PMS8 consists of a sample driven part followed by a pattern driven part. In the sample driven part we generate tuples of <italic>l</italic>
-mers originating from different strings. In the pattern driven part we generate the common <italic>d</italic>
-neighborhood of such tuples. Initially we build a matrix <italic>R</italic>
of size <italic>n</italic>
×(<italic>m</italic>
-<italic>l</italic>
+1) where row <italic>i</italic>
contains all the <italic>l</italic>
-mers in <italic>S</italic>
<sub><italic>i</italic>
</sub>
. We pick an <italic>l</italic>
-mer <italic>x</italic>
from row 1 of <italic>R</italic>
and push it on a stack. We filter out any <italic>l</italic>
-mer in <italic>R</italic>
at a distance greater than 2<italic>d</italic>
from <italic>x</italic>
. Then we pick an <italic>l</italic>
-mer from the second row of <italic>R</italic>
and push it on the stack. We filter out any <italic>l</italic>
-mer in <italic>R</italic>
that does not have a common neighbor with the <italic>l</italic>
-mers on the stack; then we repeat the process. If any row becomes empty, we discard the top of the stack, revert to the previous instance of <italic>R</italic>
and try a different <italic>l</italic>
-mer. If the stack size is above a certain threshold (see section on Memory and Runtime) we generate the common <italic>d</italic>
-neighborhood of the <italic>l</italic>
-mers on the stack. For each neighbor <italic>M</italic>
we check whether there is at least one <italic>l</italic>
-mer <italic>u</italic>
in each row of <italic>R</italic>
such that <italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>u</italic>
)≤<italic>d</italic>
. If this is true then <italic>M</italic>
is a motif. The pseudocode of PMS8 is given in Appendix 1.</p>
<p>A necessary and sufficient condition for 3 <italic>l</italic>
-mers to have a common neighbor is discussed in the section on pruning conditions. For 4 or more <italic>l</italic>
-mers we only have necessary conditions, so we may generate tuples that will not lead to solutions. However, due to the way the filtering works, the following observations apply. Let the stack at any one time contain <italic>t</italic>
<italic>l</italic>
-mers: <italic>r</italic>
<sub>1</sub>
,<italic>r</italic>
<sub>2</sub>
,…,<italic>r</italic>
<sub><italic>t</italic>
</sub>
where <italic>r</italic>
<sub><italic>t</italic>
</sub>
is at the top of the stack. Evidently, the <italic>l</italic>
-mers on the stack pass the necessary pruning conditions for <italic>t</italic>
<italic>l</italic>
-mers. However, the following are also true. For any two <italic>l</italic>
-mers <italic>r</italic>
<sub><italic>i</italic>
</sub>
and <italic>r</italic>
<sub><italic>j</italic>
</sub>
on the stack, there exists a common neighbor. This is true because whenever we filter an <italic>l</italic>
-mer we make sure it has at least one neighbor in common with the <italic>l</italic>
-mer at the stop of the stack. Thus, we can prove by induction that any two <italic>l</italic>
-mers in the stack have a common neighbor. Second, any triplet of the form <italic>r</italic>
<sub>1</sub>
,<italic>r</italic>
<sub>2</sub>
,<italic>r</italic>
<sub><italic>i</italic>
</sub>
, 2<<italic>i</italic>
≤<italic>t</italic>
, has at least one common neighbor. This is true because when the stack had only the first two <italic>l</italic>
-mers we filtered out any <italic>l</italic>
-mer which doesn’t make a compatible triplet with the two. In general, for any number <italic>p</italic>
<<italic>t</italic>
the (<italic>p</italic>
+1) tuples of the form <italic>r</italic>
<sub>1</sub>
,<italic>r</italic>
<sub>2</sub>
,…,<italic>r</italic>
<sub><italic>p</italic>
</sub>
,<italic>r</italic>
<sub><italic>i</italic>
</sub>
where <italic>p</italic>
<<italic>i</italic>
≤<italic>t</italic>
must pass the pruning conditions for <italic>p</italic>
+1<italic>l</italic>
-mers. Therefore, even though the pruning for more than 3 <italic>l</italic>
-mers is not perfect, the algorithm implicitly tests the pruning conditions on many subsets of the <italic>l</italic>
-mers in the stack and thus decreases the number of false positive tuples generated.</p>
<sec><title>Speedup techniques</title>
<sec><title>Sort rows by size</title>
<p>An important speedup technique is to reorder the rows of <italic>R</italic>
by size after every filtering step. This reduces the number of tuples that we consider at lower stack sizes. These tuples require the most expensive filtering because as the stack size increases, fewer <italic>l</italic>
-mers remain to be filtered.</p>
</sec>
<sec><title>Compress <italic>l</italic>
-mers</title>
<p>We can speed up Hamming distance operations by compressing all the l-mers of <italic>R</italic>
in advance. For example, for DNA we store 8 characters in a 16 bit integer, divided into 8 groups of 2 bits. For every 16 bit integer <italic>i</italic>
we store in a table the number of non-zero groups of bits in <italic>i</italic>
. To compute the Hamming distance between two <italic>l</italic>
-mers we first perform an exclusive or of their compressed representations. Equal characters produce bits of 0, different characters produce non-zero bits. Therefore, one table lookup provides the Hamming distance for 8 characters. One compressed <italic>l</italic>
-mer requires <italic>l</italic>
∗⌈log|<italic>Σ</italic>
|⌉ bits of storage. However, we only need the first 16 bits of this representation because the next 16 bits are the same as the first 16 bits of the <italic>l</italic>
-mer 8 positions to the right of the current one. Therefore, the table of compressed <italic>l</italic>
-mers only requires <italic>O</italic>
(<italic>n</italic>
(<italic>m</italic>
-<italic>l</italic>
+1)) words of memory.</p>
</sec>
<sec><title>Preprocess distances for pairs of <italic>l</italic>
-mers</title>
<p>The filtering step tests many times if two <italic>l</italic>
-mers have a distance of no more than 2<italic>d</italic>
. Thus, for every pair of <italic>l</italic>
-mers we compute this bit of information in advance.</p>
</sec>
<sec><title>Cache locality</title>
<p>We can update <italic>R</italic>
in an efficient manner as follows. Every row in the updated matrix <italic>R</italic>
<sup>′</sup>
is a subset of the corresponding row in the current matrix <italic>R</italic>
, because some elements will be filtered out. Therefore, we can store <italic>R</italic>
<sup>′</sup>
in the same memory locations as <italic>R</italic>
. To do this, in each row, we move the elements belonging to <italic>R</italic>
<sup>′</sup>
at the beginning of the row. In addition, we keep track of how many elements belong to <italic>R</italic>
<sup>′</sup>
. To revert from <italic>R</italic>
<sup>′</sup>
back to <italic>R</italic>
, we restore the row sizes to their previous values. The row elements will be the same even if they have been moved within the row. The same process can be repeated at every step of the recursion, therefore the whole “stack” of <italic>R</italic>
matrices is stored in a single matrix. This reduces the memory requirement and improves cache locality. The cache locality is improved because at every step of the recursion, in each row, we access a subset of the elements we accessed in the previous step, and those elements are in contiguous locations of memory.</p>
</sec>
<sec><title>Find motifs for a subset of the strings</title>
<p>We use the speedup technique described in [<xref ref-type="bibr" rid="B10">10</xref>
]: compute the motifs for <italic>n</italic>
<sup>′</sup>
<<italic>n</italic>
of the input strings, then test each of them against the remaining <italic>n</italic>
-<italic>n</italic>
<sup>′</sup>
strings. For the results in this paper <italic>n</italic>
<sup>′</sup>
was heuristically computed using the formula provided in Appendix 1.</p>
</sec>
</sec>
<sec><title>Memory and Runtime</title>
<p>Since we store all matrices <italic>R</italic>
in the space of a single matrix they only require <italic>O</italic>
(<italic>n</italic>
(<italic>m</italic>
-<italic>l</italic>
+1)) words of memory. To this we add <italic>O</italic>
(<italic>n</italic>
<sup>2</sup>
) words to store row sizes for the at most <italic>n</italic>
matrices which share the same space. The bits of information for compatible <italic>l</italic>
-mer pairs take <italic>O</italic>
((<italic>n</italic>
(<italic>m</italic>
-<italic>l</italic>
+1))<sup>2</sup>
/<italic>w</italic>
) words, where <italic>w</italic>
is the number of bits in a machine word. The table of compressed <italic>l</italic>
-mers takes <italic>O</italic>
(<italic>n</italic>
(<italic>m</italic>
-<italic>l</italic>
+1)) words. Therefore, the total memory used by the algorithm is <italic>O</italic>
(<italic>n</italic>
(<italic>n</italic>
+<italic>m</italic>
-<italic>l</italic>
+1)+(<italic>n</italic>
(<italic>m</italic>
-<italic>l</italic>
+1))<sup>2</sup>
/<italic>w</italic>
).</p>
<p>The more time we spend in the sample driven part, the less time we have to spend in the pattern driven part and vice-versa. Ideally we want to choose the threshold where we switch between the two parts such that their runtimes are almost equal. The optimal threshold can be determined empirically by running the algorithm on a small subset of the tuples. In practice, PMS8 heuristically estimates the threshold <italic>t</italic>
such that it increases with <italic>d</italic>
and |<italic>Σ</italic>
| to avoid generating very large neighborhoods and it decreases with <italic>m</italic>
to avoid spending too much time on filtering. All the results reported in this paper have been obtained using the default threshold estimation provided in Appendix 1.</p>
</sec>
<sec><title>Parallel implementation</title>
<p>We can think of <italic>m</italic>
-<italic>l</italic>
+1 independent sub problems, one for each <italic>l</italic>
-mer in the first string. The first string in each sub problem is an <italic>l</italic>
-mer of the original first string and the rest of the strings are the same as in the original input. Because of this, the problem seems to be “embarrassingly parallel.” A straightforward parallelization idea is to assign an equal number of subproblems to each processor. This method has the advantage that no inter-processor communication is necessary beyond broadcasting the input to all processors. This method would work well for algorithms where each subproblem is expected to have a similar runtime. However, for PMS8, the runtime of each subproblem is very sensitive to the size of the neighborhoods for various combinations of <italic>l</italic>
-mers and therefore some processors may end up starving while others are still busy.</p>
<p>To alleviate the above shortcoming we employ the following strategy. The processor with rank 0 is a scheduler and the others are workers. The scheduler spawns a separate worker thread to avoid using one processor just for scheduling. The scheduler reads the input and broadcasts it to all workers. Then each worker requests a sub problem from the scheduler, solves it and repeats. The scheduler loops until all jobs have been requested and all workers have been notified that no more jobs are available. At the end, all processors send their motifs to the scheduler. The scheduler loops through all the processors and collects the results. The scheduler then outputs the results.</p>
</sec>
<sec><title>Pruning conditions</title>
<p>In this section we present pruning conditions applied for filtering <italic>l</italic>
-mers in the sample driven part and for pruning enumeration trees in the pattern driven part.</p>
<p>Two <italic>l</italic>
-mers <italic>a</italic>
and <italic>b</italic>
have a common neighbor <italic>M</italic>
such that <italic>H</italic>
<italic>d</italic>
(<italic>a</italic>
,<italic>M</italic>
)≤<italic>d</italic>
<sub><italic>a</italic>
</sub>
and <italic>H</italic>
<italic>d</italic>
(<italic>b</italic>
,<italic>M</italic>
)≤<italic>d</italic>
<sub><italic>b</italic>
</sub>
if and only if <italic>H</italic>
<italic>d</italic>
(<italic>a</italic>
,<italic>b</italic>
)≤<italic>d</italic>
<sub><italic>a</italic>
</sub>
+<italic>d</italic>
<sub><italic>b</italic>
</sub>
. For 3 <italic>l</italic>
-mers, no trivial necessary and sufficient conditions have been known up to now. In [<xref ref-type="bibr" rid="B8">8</xref>
] sufficient conditions for 3 <italic>l</italic>
-mers are obtained from a preprocessed table. However, as <italic>l</italic>
increases the memory requirement of the table becomes a bottleneck. We will give simple necessary and sufficient conditions for 3 <italic>l</italic>
-mers to have a common neighbor. These conditions are also necessary for more than 3 <italic>l</italic>
-mers.</p>
<p>Let <italic>T</italic>
be a set of <italic>l</italic>
-mers and <italic>M</italic>
be an <italic>l</italic>
-mer. If ∑<italic>u</italic>
∈<italic>T</italic>
<italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>u</italic>
)>|<italic>T</italic>
|<italic>d</italic>
then, by the pigeonhole principle, one <italic>l</italic>
-mer must have a distance from <italic>M</italic>
greater than <italic>d</italic>
. Therefore, <italic>M</italic>
cannot be a common neighbor of the <italic>l</italic>
-mers in <italic>T</italic>
. If we have a lower bound on ∑<italic>u</italic>
∈<italic>T</italic>
<italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>u</italic>
) for any <italic>M</italic>
, then we can use it as a pruning condition. If the lower bound is greater than |<italic>T</italic>
|<italic>d</italic>
then there is no common neighbor for <italic>T</italic>
. One such lower bound is the <italic>consensus total distance</italic>
.</p>
<sec><title>Definition 1</title>
<p>Let <italic>T</italic>
be a set of <italic>l</italic>
-mers, where <italic>k</italic>
=|<italic>T</italic>
|. For every <italic>i</italic>
, the set <italic>T</italic>
<sub>1</sub>
[<italic>i</italic>
],<italic>T</italic>
<sub>2</sub>
[<italic>i</italic>
],..,<italic>T</italic>
<sub><italic>k</italic>
</sub>
[<italic>i</italic>
] is called the <italic>i</italic>
-th column of <italic>T</italic>
. Let <italic>m</italic>
<sub><italic>i</italic>
</sub>
be the maximum frequency of any character in column <italic>i</italic>
. Then <italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
)= ∑<italic>i</italic>
=1..<italic>l</italic>
<italic>k</italic>
-<italic>m</italic>
<sub><italic>i</italic>
</sub>
is called the consensus total distance of <italic>T</italic>
.</p>
<p>The consensus total distance is a lower bound for the total distance between any <italic>l</italic>
-mer <italic>M</italic>
and the <italic>l</italic>
-mers in <italic>T</italic>
because, regardless of <italic>M</italic>
, the distance contributed by column <italic>i</italic>
to the total distance is at least <italic>k</italic>
-<italic>m</italic>
<sub><italic>i</italic>
</sub>
. The consensus total distance for a set of two <italic>l</italic>
-mers <italic>A</italic>
and <italic>B</italic>
will be denoted by <italic>C</italic>
<italic>d</italic>
(<italic>A</italic>
,<italic>B</italic>
). Also notice that <italic>C</italic>
<italic>d</italic>
(<italic>A</italic>
,<italic>B</italic>
)=<italic>H</italic>
<italic>d</italic>
(<italic>A</italic>
,<italic>B</italic>
). We can easily prove the following lemma.</p>
</sec>
<sec><title>Lemma 1</title>
<p>Let <italic>T</italic>
be a set of <italic>l</italic>
-mers and <italic>k</italic>
=|<italic>T</italic>
|. Let <italic>d</italic>
<sub>1</sub>
,<italic>d</italic>
<sub>2</sub>
,…<italic>d</italic>
<sub><italic>k</italic>
</sub>
be non-negative integers. There exists a <italic>l</italic>
-mer <italic>M</italic>
such that <italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>i</italic>
</sub>
)≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
,∀<italic>i</italic>
, only if <inline-formula><mml:math id="M1" name="1471-2105-15-34-i1" overflow="scroll"><mml:mtext mathvariant="italic">Cd</mml:mtext>
<mml:mo>(</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>≤</mml:mo>
<mml:msubsup><mml:mrow><mml:mi>Σ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:msub><mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
</mml:math>
</inline-formula>
.</p>
</sec>
<sec><title>Theorem 1</title>
<p>Let <italic>T</italic>
be a set of 3 <italic>l</italic>
-mers and <italic>d</italic>
<sub>1</sub>
,<italic>d</italic>
<sub>2</sub>
,<italic>d</italic>
<sub>3</sub>
be non-negative integers. There exists a <italic>l</italic>
-mer <italic>M</italic>
such that <italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>i</italic>
</sub>
)≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
,∀<italic>i</italic>
,1≤<italic>i</italic>
≤3 if and only if the following conditions hold:</p>
<p><bold>i)</bold>
<italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
)≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
+<italic>d</italic>
<sub><italic>j</italic>
</sub>
,∀<italic>i</italic>
,<italic>j</italic>
,1≤<italic>i</italic>
<<italic>j</italic>
≤3</p>
<p><bold>ii)</bold>
<italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
)≤<italic>d</italic>
<sub>1</sub>
+<italic>d</italic>
<sub>2</sub>
+<italic>d</italic>
<sub>3</sub>
</p>
</sec>
<sec><title><italic>Proof</italic>
</title>
<p>The “only if” part follows from lemma 1.</p>
<p>For the “if” part we show how to construct a common neighbor <italic>M</italic>
provided that the conditions hold. We say that a column <italic>k</italic>
where <italic>T</italic>
<sub>1</sub>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>2</sub>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>3</sub>
[ <italic>k</italic>
] is of type <italic>N</italic>
<sub>0</sub>
. If <italic>T</italic>
<sub>1</sub>
[ <italic>k</italic>
]≠<italic>T</italic>
<sub>2</sub>
[<italic>k</italic>
]=<italic>T</italic>
<sub>3</sub>
[ <italic>k</italic>
] then the column is of type <italic>N</italic>
<sub>1</sub>
. If <italic>T</italic>
<sub>1</sub>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>3</sub>
[ <italic>k</italic>
]≠<italic>T</italic>
<sub>2</sub>
[ <italic>k</italic>
] the column is of type <italic>N</italic>
<sub>2</sub>
and if <italic>T</italic>
<sub>1</sub>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>2</sub>
[ <italic>k</italic>
]≠<italic>T</italic>
<sub>3</sub>
[ <italic>k</italic>
] then the column is of type <italic>N</italic>
<sub>3</sub>
. If all three characters in the column are distinct, the column is of type <italic>N</italic>
<sub>4</sub>
. Let <italic>n</italic>
<sub><italic>i</italic>
</sub>
,∀<italic>i</italic>
,0≤<italic>i</italic>
≤4 be the number of columns of type <italic>N</italic>
<sub><italic>i</italic>
</sub>
. Consider two cases:</p>
<p>Case 1) There exists <italic>i</italic>
,1≤<italic>i</italic>
≤3 for which <italic>n</italic>
<sub><italic>i</italic>
</sub>
≥<italic>d</italic>
<sub><italic>i</italic>
</sub>
. We construct <italic>M</italic>
as illustrated in Figure <xref ref-type="fig" rid="F1">1</xref>
. Pick <italic>d</italic>
<sub><italic>i</italic>
</sub>
columns of type <italic>n</italic>
<sub><italic>i</italic>
</sub>
. For each chosen column <italic>k</italic>
set <italic>M</italic>
[ <italic>k</italic>
]=<italic>T</italic>
<sub><italic>j</italic>
</sub>
[ <italic>k</italic>
] where <italic>j</italic>
≠<italic>i</italic>
. For all other columns set <italic>M</italic>
[ <italic>k</italic>
]=<italic>T</italic>
<sub><italic>i</italic>
</sub>
[ <italic>k</italic>
]. Therefore <italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>M</italic>
)=<italic>d</italic>
<sub><italic>i</italic>
</sub>
. For <italic>j</italic>
≠<italic>i</italic>
we know that <italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
)≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
+<italic>d</italic>
<sub><italic>j</italic>
</sub>
from condition <bold>i)</bold>
(condition <bold>i</bold>
is assumed to be true at this point because we are proving the “if” part). We also know that <italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>M</italic>
)+<italic>C</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
)≤<italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
) from the triangle inequality. It follows that <italic>C</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
)≤<italic>d</italic>
<sub><italic>j</italic>
</sub>
. Since <italic>C</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
)=<italic>H</italic>
<italic>d</italic>
(<italic>M</italic>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
) it means that <italic>M</italic>
is indeed a common neighbor of the three <italic>l</italic>
-mers.</p>
<fig id="F1" position="float"><label>Figure 1</label>
<caption><p><bold>Proof of theorem 1, case 1.</bold>
Proof of theorem 1, case 1: There exists <italic>i</italic>
,1≤<italic>i</italic>
≤3 for which <italic>n</italic>
<sub><italic>i</italic>
</sub>
≥<italic>d</italic>
<sub><italic>i</italic>
</sub>
. Without loss of generality we assume <italic>i</italic>
=1. The top 3 rows represent the input <italic>l</italic>
-mers. The last row shows a common neighbor <italic>M</italic>
. In any column, identical colors represents matches, different colors represent mismatches.</p>
</caption>
<graphic xlink:href="1471-2105-15-34-1"></graphic>
</fig>
<p>Case 2) For all <italic>i</italic>
,1≤<italic>i</italic>
≤3 we have <italic>n</italic>
<sub><italic>i</italic>
</sub>
<<italic>d</italic>
<sub><italic>i</italic>
</sub>
. We construct <italic>M</italic>
as shown in Figure <xref ref-type="fig" rid="F2">2</xref>
. For columns <italic>k</italic>
of type <italic>N</italic>
<sub>0</sub>
,<italic>N</italic>
<sub>2</sub>
and <italic>N</italic>
<sub>3</sub>
we set <italic>M</italic>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>1</sub>
[ <italic>k</italic>
]. For columns of type <italic>N</italic>
<sub>1</sub>
we set <italic>M</italic>
[ <italic>k</italic>
]=<italic>T</italic>
<sub>2</sub>
[ <italic>k</italic>
]. For any <italic>i</italic>
,1≤<italic>i</italic>
≤3 the following applies. If <italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
then the Hamming distance between <italic>M</italic>
and <italic>T</italic>
<sub><italic>i</italic>
</sub>
is less than <italic>d</italic>
<sub><italic>i</italic>
</sub>
regardless of what characters we choose for <italic>M</italic>
in the columns of type <italic>N</italic>
<sub>4</sub>
. On the other hand, if <italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
><italic>d</italic>
<sub><italic>i</italic>
</sub>
then <italic>M</italic>
and <italic>T</italic>
<sub><italic>i</italic>
</sub>
have to match in at least <italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
-<italic>d</italic>
<sub><italic>i</italic>
</sub>
columns of type <italic>N</italic>
<sub>4</sub>
. Thus, we pick <italic>m</italic>
<italic>a</italic>
<italic>x</italic>
(0,<italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
-<italic>d</italic>
<sub><italic>i</italic>
</sub>
) columns of type <italic>N</italic>
<sub>4</sub>
and for each such column <italic>k</italic>
we set <italic>M</italic>
[ <italic>k</italic>
]=<italic>T</italic>
<sub><italic>i</italic>
</sub>
[ <italic>k</italic>
]. Now we prove that we actually have enough columns to make the above choices, in other words <inline-formula><mml:math id="M2" name="1471-2105-15-34-i2" overflow="scroll"><mml:msubsup><mml:mrow><mml:mi>Σ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msubsup>
<mml:mtext mathvariant="italic">max</mml:mtext>
<mml:mo>(</mml:mo>
<mml:mn>0</mml:mn>
<mml:mo>,</mml:mo>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>+</mml:mo>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>4</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>-</mml:mo>
<mml:msub><mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>)</mml:mo>
<mml:mo>≤</mml:mo>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>4</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
</inline-formula>
. This is equivalent to the following conditions being true: </p>
<p><bold>a)</bold>
For any <italic>i</italic>
,1≤<italic>i</italic>
≤3 we want <italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
-<italic>d</italic>
<sub><italic>i</italic>
</sub>
≤<italic>n</italic>
<sub>4</sub>
. This is true because <italic>n</italic>
<sub><italic>i</italic>
</sub>
<<italic>d</italic>
<sub><italic>i</italic>
</sub>
.</p>
<p><bold>b)</bold>
For any <italic>i</italic>
,<italic>j</italic>
,1≤<italic>i</italic>
<<italic>j</italic>
≤3 we want (<italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
-<italic>d</italic>
<sub><italic>i</italic>
</sub>
)+(<italic>n</italic>
<sub><italic>j</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
-<italic>d</italic>
<sub><italic>j</italic>
</sub>
)≤<italic>n</italic>
<sub>4</sub>
. This can be rewritten as <italic>n</italic>
<sub><italic>i</italic>
</sub>
+<italic>n</italic>
<sub><italic>j</italic>
</sub>
+<italic>n</italic>
<sub>4</sub>
≤<italic>d</italic>
<sub><italic>i</italic>
</sub>
+<italic>d</italic>
<sub><italic>j</italic>
</sub>
. The left hand side is <italic>H</italic>
<italic>d</italic>
(<italic>T</italic>
<sub><italic>i</italic>
</sub>
,<italic>T</italic>
<sub><italic>j</italic>
</sub>
) which we know is less or equal to <italic>d</italic>
<sub><italic>i</italic>
</sub>
+<italic>d</italic>
<sub><italic>j</italic>
</sub>
.</p>
<p><bold>c)</bold>
We want <inline-formula><mml:math id="M3" name="1471-2105-15-34-i3" overflow="scroll"><mml:msubsup><mml:mrow><mml:mi>Σ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msubsup>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>+</mml:mo>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>4</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>-</mml:mo>
<mml:msub><mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>≤</mml:mo>
<mml:msub><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>4</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
</inline-formula>
. This can be rewritten as <italic>n</italic>
<sub>1</sub>
+<italic>n</italic>
<sub>2</sub>
+<italic>n</italic>
<sub>3</sub>
+2<italic>n</italic>
<sub>4</sub>
≤<italic>d</italic>
<sub>1</sub>
+<italic>d</italic>
<sub>2</sub>
+<italic>d</italic>
<sub>3</sub>
. The left hand side is <italic>C</italic>
<italic>d</italic>
(<italic>T</italic>
) which we know is less than <italic>d</italic>
<sub>1</sub>
+<italic>d</italic>
<sub>2</sub>
+<italic>d</italic>
<sub>3</sub>
.</p>
<fig id="F2" position="float"><label>Figure 2</label>
<caption><p><bold>Proof of theorem 1, case 2.</bold>
Proof of theorem 1, case 2: <italic>n</italic>
<sub><italic>i</italic>
</sub>
<<italic>d</italic>
<sub><italic>i</italic>
</sub>
for all <italic>i</italic>
, 1≤<italic>i</italic>
≤3. The top 3 rows represent the input <italic>l</italic>
-mers. The last row shows a common neighbor <italic>M</italic>
. In any column, identical colors represents matches, different colors represent mismatches.</p>
</caption>
<graphic xlink:href="1471-2105-15-34-2"></graphic>
</fig>
<p>One of our reviewers kindly pointed out that the above proof is similar to an algorithm in [<xref ref-type="bibr" rid="B11">11</xref>
].</p>
</sec>
</sec>
</sec>
<sec><title>Results and discussion</title>
<p>PMS8 is implemented in C++ and uses OpenMPI for communication between processors. PMS8 was evaluated on the Hornet cluster in the Booth Engineering Center for Advanced Technology (BECAT) at University of Connecticut. The Hornet cluster consists of 64 nodes, each equipped with 12 Intel Xeon X5650 Westmere cores and 48 GB of RAM. The nodes use Infiniband networking for MPI. In our experiments we employed at most 48 cores on at most 4 nodes.</p>
<p>We generated random (<italic>l</italic>
,<italic>d</italic>
) instances according to [<xref ref-type="bibr" rid="B1">1</xref>
] and as described in the introduction. For every (<italic>l</italic>
,<italic>d</italic>
) combination we report the average runtime over 5 random instances. For several challenging instances, in Figure <xref ref-type="fig" rid="F3">3</xref>
we present the speedup obtained by the parallel version over the single core version. For <italic>p</italic>
=48 cores the speedup is close to <italic>S</italic>
=45 and thus the efficiency is <italic>E</italic>
=<italic>S</italic>
/<italic>p</italic>
=94<italic>%</italic>
.</p>
<fig id="F3" position="float"><label>Figure 3</label>
<caption><p><bold>Speedup of the parallel implementation over the single core version.</bold>
Speedup of the multi-core version of PMS8 over the single core version, for several datasets.</p>
</caption>
<graphic xlink:href="1471-2105-15-34-3"></graphic>
</fig>
<p>In Figure <xref ref-type="fig" rid="F4">4</xref>
we show the effect of the first speedup technique (sorthing rows by size) on the runtime. Note that all other speedups are enabled, only sorting rows by size is varied. The figure shows that sorting the rows by size improves the speed of PMS8 by 25% to 50%.</p>
<fig id="F4" position="float"><label>Figure 4</label>
<caption><p><bold>The effect of the “sort rows by size” speedup on runtime.</bold>
Comparison between PMS8 and PMS8 without sorting rows by size (see the section on Speedup techniques). Note that, in both versions, all the other speedups are enabled. The runtimes are for single core execution, averaged over 5 random instances.</p>
</caption>
<graphic xlink:href="1471-2105-15-34-4"></graphic>
</fig>
<p>The runtime of PMS8 on instances with <italic>l</italic>
up to 50 and <italic>d</italic>
up to 21 is shown in Figure <xref ref-type="fig" rid="F5">5</xref>
. Instances which are expected to have more than 500 motifs simply by random chance (spurious motifs) are excluded. The expected number of spurious motifs was computed as described in Appendix 1. Instances where <italic>d</italic>
is small relative to <italic>l</italic>
are solved efficiently using a single CPU core. For more challenging instances we report the time taken using 48 cores.</p>
<fig id="F5" position="float"><label>Figure 5</label>
<caption><p><bold>PMS8 runtimes for multiple combinations of </bold>
<bold><italic>l</italic>
</bold>
<bold> and </bold>
<bold><italic>d</italic>
</bold>
<bold>.</bold>
PMS8 runtimes for datasets with <italic>l</italic>
up to 50 and <italic>d</italic>
up to 25 averaged over 5 random datasets. White background signifies single core execution. Blue background signifies execution using 48 cores. Instances in gray have more than 500 spurious motifs. Orange cells indicate unsolved instances. Time is reported in hours (h), minutes (m) and seconds (s).</p>
</caption>
<graphic xlink:href="1471-2105-15-34-5"></graphic>
</fig>
<p>A comparison between PMS8 and qPMS7 [<xref ref-type="bibr" rid="B5">5</xref>
] on challenging instances is shown in Table <xref ref-type="table" rid="T1">1</xref>
. Both programs have been executed on the Hornet cluster. qPMS7 is a sequential algorithm. PMS8 was evaluated using up to 48 cores. The speedup of PMS8 single core over qPMS7 is shown in Figure <xref ref-type="fig" rid="F6">6</xref>
. The speedup is high for small instances because qPMS7 has to load an ILP table. For larger instances the speedup of PMS8 sharply increases. This is expected because qPMS7 always generates neighborhoods for tuples of 3 <italic>l</italic>
-mers, which become very large as <italic>l</italic>
and <italic>d</italic>
grow. On the other hand, PMS8 increases the number of <italic>l</italic>
-mers in the tuple with the instance size. With each <italic>l</italic>
-mer added to the tuple, the size of the neighborhood reduces exponentially, whereas the number of neighborhoods generated increases by a linear factor. The ILP table precomputation requires solving many ILP formulations. The table then makes qPMS7 less memory efficient than PMS8. The peak memory used by qPMS7 for the challenging instances in Table <xref ref-type="table" rid="T1">1</xref>
was 607 MB whereas for PMS8 it was 122 MB. Furthermore, due to the size of the ILP table, qPMS7 is not able to solve any instances where <italic>l</italic>
>23. PMS8 is the first algorithm to solve the challenging instances (25,10) and (26,11).</p>
<table-wrap position="float" id="T1"><label>Table 1</label>
<caption><p>Comparison between qPMS7 and PMS8</p>
</caption>
<table frame="hsides" rules="groups" border="1"><colgroup><col align="left"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
</colgroup>
<thead valign="top"><tr><th align="left"><bold>Instance</bold>
</th>
<th align="center"><bold>qPMS7</bold>
</th>
<th align="center"><bold>PMS8</bold>
<sup><bold>1</bold>
</sup>
</th>
<th align="center"><bold>PMS8</bold>
<sup><bold>16</bold>
</sup>
</th>
<th align="center"><bold>PMS8</bold>
<sup><bold>32</bold>
</sup>
</th>
<th align="center"><bold>PMS8</bold>
<sup><bold>48</bold>
</sup>
</th>
</tr>
</thead>
<tbody valign="top"><tr><td align="left" valign="bottom">(13,4)<hr></hr>
</td>
<td align="center" valign="bottom">29s<hr></hr>
</td>
<td align="center" valign="bottom">7s<hr></hr>
</td>
<td align="center" valign="bottom">3s<hr></hr>
</td>
<td align="center" valign="bottom">2s<hr></hr>
</td>
<td align="center" valign="bottom">2s<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(15,5)<hr></hr>
</td>
<td align="center" valign="bottom">2.1m<hr></hr>
</td>
<td align="center" valign="bottom">48s<hr></hr>
</td>
<td align="center" valign="bottom">5s<hr></hr>
</td>
<td align="center" valign="bottom">4s<hr></hr>
</td>
<td align="center" valign="bottom">3s<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(17,6)<hr></hr>
</td>
<td align="center" valign="bottom">10.3m<hr></hr>
</td>
<td align="center" valign="bottom">5.2m<hr></hr>
</td>
<td align="center" valign="bottom">22s<hr></hr>
</td>
<td align="center" valign="bottom">12s<hr></hr>
</td>
<td align="center" valign="bottom">9s<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(19,7)<hr></hr>
</td>
<td align="center" valign="bottom">54.6m<hr></hr>
</td>
<td align="center" valign="bottom">26.6m<hr></hr>
</td>
<td align="center" valign="bottom">1.7m<hr></hr>
</td>
<td align="center" valign="bottom">52s<hr></hr>
</td>
<td align="center" valign="bottom">37s<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="center" valign="bottom">4.87h<hr></hr>
</td>
<td align="center" valign="bottom">1.64h<hr></hr>
</td>
<td align="center" valign="bottom">6.5m<hr></hr>
</td>
<td align="center" valign="bottom">3.3m<hr></hr>
</td>
<td align="center" valign="bottom">2.2m<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(23,9)<hr></hr>
</td>
<td align="center" valign="bottom">27.09h<hr></hr>
</td>
<td align="center" valign="bottom">5.48h<hr></hr>
</td>
<td align="center" valign="bottom">21.1m<hr></hr>
</td>
<td align="center" valign="bottom">10.7m<hr></hr>
</td>
<td align="center" valign="bottom">7.4m<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(25,10)<hr></hr>
</td>
<td align="center" valign="bottom">-<hr></hr>
</td>
<td align="center" valign="bottom">15.45h<hr></hr>
</td>
<td align="center" valign="bottom">1.01h<hr></hr>
</td>
<td align="center" valign="bottom">30.4m<hr></hr>
</td>
<td align="center" valign="bottom">20.7m<hr></hr>
</td>
</tr>
<tr><td align="left">(26,11)</td>
<td align="center">-</td>
<td align="center">-</td>
<td align="center">-</td>
<td align="center">-</td>
<td align="center">46.9h</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>Comparison between qPMS7 and PMS8 on challenging instances. PMS8<sup><italic>P</italic>
</sup>
means PMS8 used <italic>P</italic>
CPU cores. Both programs have been executed on the same hardware and the same datasets. The times are average runtimes over 5 instances for each dataset.</p>
</table-wrap-foot>
</table-wrap>
<fig id="F6" position="float"><label>Figure 6</label>
<caption><p><bold>Speedup of PMS8 single core over qPMS7.</bold>
Ratio of runtimes between qPMS7 and PMS8 running on a single core. Both programs have been executed on the same hardware and the same datasets. The times are average runtimes over 5 instances for each dataset.</p>
</caption>
<graphic xlink:href="1471-2105-15-34-6"></graphic>
</fig>
<p>Some recent results in the literature have also focused on instances other than the challenging ones presented above. A summary of these results and a comparison with PMS8 is presented in Table <xref ref-type="table" rid="T2">2</xref>
, starting with the most recent results. These results have been obtained on various types of hardware: single core, multi-core, GPU, grid. In the comparison, we try to match the number of processors whenever possible. The speed difference is of several orders of magnitude in some cases which indicates that the pruning conditions employed by PMS8 exponentially reduce the search space compared to other algorithms.</p>
<table-wrap position="float" id="T2"><label>Table 2</label>
<caption><p>Comparison between PMS8 and recent results in the literature</p>
</caption>
<table frame="hsides" rules="groups" border="1"><colgroup><col align="left"></col>
<col align="left"></col>
<col align="left"></col>
<col align="left"></col>
<col align="left"></col>
<col align="left"></col>
</colgroup>
<thead valign="top"><tr><th align="left"><bold>Previous algorithm</bold>
</th>
<th align="left"><bold>Instance</bold>
</th>
<th align="left"><bold>Time</bold>
</th>
<th align="left"><bold>Cores</bold>
</th>
<th align="left"><bold>PMS8 time</bold>
</th>
<th align="left"><bold>PMS8 cores</bold>
</th>
</tr>
</thead>
<tbody valign="top"><tr><td align="left" valign="bottom">Abbas et al. 2012 [<xref ref-type="bibr" rid="B12">12</xref>
], PHEP_PMSprune<hr></hr>
</td>
<td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="left" valign="bottom">20.42h<hr></hr>
</td>
<td align="left" valign="bottom">8<hr></hr>
</td>
<td align="left" valign="bottom">6.5m<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Yu et al. 2012 [<xref ref-type="bibr" rid="B3">3</xref>
], PairMotif<hr></hr>
</td>
<td align="left" valign="bottom">(27, 9)<hr></hr>
</td>
<td align="left" valign="bottom">10h<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">4s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td rowspan="2" align="left" valign="middle">Desaraju and Mukkamala 2011 [<xref ref-type="bibr" rid="B7">7</xref>
]<hr></hr>
</td>
<td align="left" valign="bottom">(24,6)<hr></hr>
</td>
<td align="left" valign="bottom">347s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">1s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(48,12)<hr></hr>
</td>
<td align="left" valign="bottom">188s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">1s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td rowspan="2" align="left" valign="middle">Dasari et al. 2011 [<xref ref-type="bibr" rid="B13">13</xref>
], mSPELLER / gSPELLER<hr></hr>
</td>
<td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="left" valign="bottom">3.7h<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
<td align="left" valign="bottom">6.5m<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="left" valign="bottom">2.2h<hr></hr>
</td>
<td rowspan="2" align="left" valign="middle">4 GPUs x 240 cores<hr></hr>
</td>
<td align="left" valign="bottom">6.5m<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Dasari et al. 2010 [<xref ref-type="bibr" rid="B14">14</xref>
], BitBased<hr></hr>
</td>
<td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="left" valign="bottom">1.1h<hr></hr>
</td>
<td align="left" valign="bottom">6.5m<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Dasari and Desh 2010 [<xref ref-type="bibr" rid="B15">15</xref>
], BitBased<hr></hr>
</td>
<td align="left" valign="bottom">(21,8)<hr></hr>
</td>
<td align="left" valign="bottom">6.9h<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
<td align="left" valign="bottom">6.5m<hr></hr>
</td>
<td align="left" valign="bottom">16<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Sahoo et al. 2011 [<xref ref-type="bibr" rid="B16">16</xref>
]<hr></hr>
</td>
<td align="left" valign="bottom">(16,4)<hr></hr>
</td>
<td align="left" valign="bottom">106s<hr></hr>
</td>
<td align="left" valign="bottom">4<hr></hr>
</td>
<td align="left" valign="bottom">1s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Sun et al. 2011 [<xref ref-type="bibr" rid="B17">17</xref>
], TreeMotif<hr></hr>
</td>
<td align="left" valign="bottom">(40,14)<hr></hr>
</td>
<td align="left" valign="bottom">6h<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">6s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">He et al. 2010 [<xref ref-type="bibr" rid="B18">18</xref>
], ListMotif<hr></hr>
</td>
<td align="left" valign="bottom">(40,14)<hr></hr>
</td>
<td align="left" valign="bottom">28,087s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">6s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">Faheem 2010 [<xref ref-type="bibr" rid="B19">19</xref>
], skip-Brute Force<hr></hr>
</td>
<td align="left" valign="bottom">(15,4)<hr></hr>
</td>
<td align="left" valign="bottom">2934s<hr></hr>
</td>
<td align="left" valign="bottom">96 nodes<hr></hr>
</td>
<td align="left" valign="bottom">1s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td rowspan="3" align="left" valign="middle">Ho et al. 2009 [<xref ref-type="bibr" rid="B6">6</xref>
], iTriplet</td>
<td align="left" valign="bottom">(24,8)<hr></hr>
</td>
<td align="left" valign="bottom">4h<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">5s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">(38,12)<hr></hr>
</td>
<td align="left" valign="bottom">1h<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
<td align="left" valign="bottom">1s<hr></hr>
</td>
<td align="left" valign="bottom">1<hr></hr>
</td>
</tr>
<tr><td align="left">(40,12)</td>
<td align="left">5m</td>
<td align="left">1</td>
<td align="left">1s</td>
<td align="left">1</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>Side by side comparison between PMS8 and recent results in the literature. Time is reported in seconds (s), minutes (m) or hours (h). Note that the hardware is different, though we tried to match the number of processors when possible. Also, the instances are randomly generated using the same algorithm, however the actual instances used by the various papers are most likely different. For PMS8, the times are averages over 5 randomly generated instances.</p>
</table-wrap-foot>
</table-wrap>
<p>We also compared PMS8 with qPMS7 on the real datasets discussed in [<xref ref-type="bibr" rid="B20">20</xref>
]. We excluded datasets with less than 4 input sequences because these are not very challenging. For each dataset we chose two combinations of <italic>l</italic>
and <italic>d</italic>
. These combinations were chosen on a dataset basis because for large values of <italic>d</italic>
the number of reported motifs is excessive and for small values of <italic>d</italic>
the instance is not very challenging. To make qPMS7 behave like PMS8 we set the quorum percent to 100% (<italic>q</italic>
=<italic>n</italic>
). In Table <xref ref-type="table" rid="T3">3</xref>
we report the dataset name, the total number of sequences, the total number of bases in each dataset, the <italic>l</italic>
and <italic>d</italic>
combination and the runtimes of the two algorithms. Note that both algorithms are exact algorithms and therefore the sensitivity and specificity are the same. Similar to the comparison on synthetic data, the comparison on real data reveals that PMS8 outperforms qPMS7.</p>
<table-wrap position="float" id="T3"><label>Table 3</label>
<caption><p><bold>Runtime comparison between PMS8 and qPMS7 on real datasets from [</bold>
[<xref ref-type="bibr" rid="B20">20</xref>
]<bold>]</bold>
</p>
</caption>
<table frame="hsides" rules="groups" border="1"><colgroup><col align="left"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
<col align="center"></col>
</colgroup>
<thead valign="top"><tr><th align="left"><bold>Dataset</bold>
</th>
<th align="center"><bold>n</bold>
</th>
<th align="center"><bold>Total no. bases</bold>
</th>
<th align="center"><bold>l</bold>
</th>
<th align="center"><bold>d</bold>
</th>
<th align="center"><bold>PMS8 time</bold>
</th>
<th align="center"><bold>qPMS7 time</bold>
</th>
</tr>
</thead>
<tbody valign="top"><tr><td align="left" valign="bottom">dm01r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">55<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">dm01r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">dm04r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">8000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">dm04r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">8000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm01r<hr></hr>
</td>
<td align="center" valign="bottom">18<hr></hr>
</td>
<td align="center" valign="bottom">36000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">10<hr></hr>
</td>
<td align="center" valign="bottom">14<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm01r<hr></hr>
</td>
<td align="center" valign="bottom">18<hr></hr>
</td>
<td align="center" valign="bottom">36000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">25<hr></hr>
</td>
<td align="center" valign="bottom">40<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm02r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">11<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm02r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">35<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm03r<hr></hr>
</td>
<td align="center" valign="bottom">10<hr></hr>
</td>
<td align="center" valign="bottom">15000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">3<hr></hr>
</td>
<td align="center" valign="bottom">24<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm03r<hr></hr>
</td>
<td align="center" valign="bottom">10<hr></hr>
</td>
<td align="center" valign="bottom">15000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">14<hr></hr>
</td>
<td align="center" valign="bottom">146<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm04r<hr></hr>
</td>
<td align="center" valign="bottom">13<hr></hr>
</td>
<td align="center" valign="bottom">26000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">44<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm04r<hr></hr>
</td>
<td align="center" valign="bottom">13<hr></hr>
</td>
<td align="center" valign="bottom">26000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">15<hr></hr>
</td>
<td align="center" valign="bottom">39<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm05r<hr></hr>
</td>
<td align="center" valign="bottom">3<hr></hr>
</td>
<td align="center" valign="bottom">3000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm05r<hr></hr>
</td>
<td align="center" valign="bottom">3<hr></hr>
</td>
<td align="center" valign="bottom">3000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">46<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm08r<hr></hr>
</td>
<td align="center" valign="bottom">15<hr></hr>
</td>
<td align="center" valign="bottom">7500<hr></hr>
</td>
<td align="center" valign="bottom">17<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm08r<hr></hr>
</td>
<td align="center" valign="bottom">15<hr></hr>
</td>
<td align="center" valign="bottom">7500<hr></hr>
</td>
<td align="center" valign="bottom">17<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">46<hr></hr>
</td>
<td align="center" valign="bottom">251<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm19r<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">2500<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm19r<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">2500<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm20r<hr></hr>
</td>
<td align="center" valign="bottom">35<hr></hr>
</td>
<td align="center" valign="bottom">70000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">27<hr></hr>
</td>
<td align="center" valign="bottom">32<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm20r<hr></hr>
</td>
<td align="center" valign="bottom">35<hr></hr>
</td>
<td align="center" valign="bottom">70000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">56<hr></hr>
</td>
<td align="center" valign="bottom">136<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm26r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">hm26r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">46<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus02r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">11<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus02r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">45<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus04r<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">7000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">15<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus04r<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">7000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">22<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus05r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">2000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">79<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus05r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">2000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus07r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">79<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus07r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus10r<hr></hr>
</td>
<td align="center" valign="bottom">13<hr></hr>
</td>
<td align="center" valign="bottom">13000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">56<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus10r<hr></hr>
</td>
<td align="center" valign="bottom">13<hr></hr>
</td>
<td align="center" valign="bottom">13000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">70<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus11r<hr></hr>
</td>
<td align="center" valign="bottom">12<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
<td align="center" valign="bottom">150<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">mus11r<hr></hr>
</td>
<td align="center" valign="bottom">12<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">938<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst01r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">14<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst01r<hr></hr>
</td>
<td align="center" valign="bottom">9<hr></hr>
</td>
<td align="center" valign="bottom">9000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
<td align="center" valign="bottom">63<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst02r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">2000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst02r<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">2000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst03r<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
<td align="center" valign="bottom">4000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst03r<hr></hr>
</td>
<td align="center" valign="bottom">8<hr></hr>
</td>
<td align="center" valign="bottom">4000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">19<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst04r<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst04r<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">6000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst05r<hr></hr>
</td>
<td align="center" valign="bottom">3<hr></hr>
</td>
<td align="center" valign="bottom">1500<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">4<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst05r<hr></hr>
</td>
<td align="center" valign="bottom">3<hr></hr>
</td>
<td align="center" valign="bottom">1500<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst06r<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">3500<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst06r<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">3500<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">7<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">12<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst08r<hr></hr>
</td>
<td align="center" valign="bottom">11<hr></hr>
</td>
<td align="center" valign="bottom">11000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">5<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst08r<hr></hr>
</td>
<td align="center" valign="bottom">11<hr></hr>
</td>
<td align="center" valign="bottom">11000<hr></hr>
</td>
<td align="center" valign="bottom">23<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">1<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
</tr>
<tr><td align="left" valign="bottom">yst09r<hr></hr>
</td>
<td align="center" valign="bottom">16<hr></hr>
</td>
<td align="center" valign="bottom">16000<hr></hr>
</td>
<td align="center" valign="bottom">21<hr></hr>
</td>
<td align="center" valign="bottom">6<hr></hr>
</td>
<td align="center" valign="bottom">2<hr></hr>
</td>
<td align="center" valign="bottom">17<hr></hr>
</td>
</tr>
<tr><td align="left">yst09r</td>
<td align="center">16</td>
<td align="center">16000</td>
<td align="center">23</td>
<td align="center">7</td>
<td align="center">6</td>
<td align="center">68</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>For each dataset we tested two combinations of <italic>l</italic>
and <italic>d</italic>
. For qPMS7 we set <italic>q</italic>
=<italic>n</italic>
. Both algorithms were executed on a single CPU core. Time is reported in seconds, rounded up to the next second.</p>
</table-wrap-foot>
</table-wrap>
</sec>
<sec sec-type="conclusions"><title>Conclusions</title>
<p>We have presented PMS8, an efficient algorithm for the PMS problem. PMS8 is able to efficiently generate neighborhoods for <italic>t</italic>
<italic>l</italic>
-mers at a time, by using the pruning conditions presented in this paper. Previous algorithms generate neighborhoods for only up to three <italic>l</italic>
-mers at a time whereas in PMS8 the value of <italic>t</italic>
is increased as the instances become more challenging and therefore the exponential explosion is postponed. The second reason for the efficiency of PMS8 comes from the careful implementation which employs several speedup techniques and emphasizes cache locality.</p>
</sec>
<sec><title>Appendix</title>
<sec><title>Appendix 1 Generating neighborhoods</title>
<p><bold>Algorithm 1. GenerateNeighborhood</bold>
(<italic>T</italic>
,<italic>d</italic>
)<disp-formula><graphic xlink:href="1471-2105-15-34-i4.gif"></graphic>
</disp-formula>
</p>
</sec>
<sec><title>Appendix 2 PMS8 pseudocode</title>
<p><bold>Algorithm 2. PMS8</bold>
(<italic>T</italic>
,<italic>d</italic>
)<disp-formula><graphic xlink:href="1471-2105-15-34-i5.gif"></graphic>
</disp-formula>
</p>
</sec>
<sec><title>Appendix 3 Challenging instances</title>
<p>For a fixed <italic>l</italic>
, as <italic>d</italic>
increases, the instance becomes more challenging. However, as <italic>d</italic>
increases, the number of false positives also increases, because many motifs will appear simply by random chance. The expected number of spurious motifs in a random instance can be estimated as follows (see e.g., [<xref ref-type="bibr" rid="B4">4</xref>
]). The number of <italic>l</italic>
-mers in the neighborhood of a given <italic>l</italic>
-mer <italic>M</italic>
is <inline-formula><mml:math id="M4" name="1471-2105-15-34-i6" overflow="scroll"><mml:mi>N</mml:mi>
<mml:mo>(</mml:mo>
<mml:mi>Σ</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>l</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>d</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:msubsup><mml:mrow><mml:mi>Σ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>0</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:msubsup><mml:mrow><mml:mo>(</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>l</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>)</mml:mo>
<mml:msup><mml:mrow><mml:mo>(</mml:mo>
<mml:mo>|</mml:mo>
<mml:mi>Σ</mml:mi>
<mml:mo>|</mml:mo>
<mml:mo>-</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>d</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
</inline-formula>
. The probability that <italic>M</italic>
is a <italic>d</italic>
-neighbor of a random <italic>l</italic>
-mer is <italic>p</italic>
(<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
)=<italic>N</italic>
(<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
)/|<italic>Σ</italic>
|<sup><italic>l</italic>
</sup>
. The probability that <italic>M</italic>
has at least one <italic>d</italic>
-neighbor among the <italic>l</italic>
-mers of a string of length <italic>m</italic>
is thus <italic>q</italic>
(<italic>m</italic>
,<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
)=1-(1-<italic>p</italic>
(<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
))<sup><italic>m</italic>
-<italic>l</italic>
+1</sup>
. The probability that <italic>M</italic>
has at least one <italic>d</italic>
-neighbor in each of <italic>n</italic>
random strings of length <italic>m</italic>
is <italic>q</italic>
(<italic>m</italic>
,<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
)<sup><italic>n</italic>
</sup>
. Finally, the expected number of spurious motifs in an instance with <italic>n</italic>
strings of length <italic>m</italic>
each is: |<italic>Σ</italic>
|<sup><italic>l</italic>
</sup>
<italic>q</italic>
(<italic>m</italic>
,<italic>Σ</italic>
,<italic>l</italic>
,<italic>d</italic>
)<sup><italic>n</italic>
</sup>
. In this paper we consider all combinations of <italic>l</italic>
and <italic>d</italic>
where <italic>l</italic>
is at most 50 and the number of spurious motifs (expected by random chance) does not exceed 500. Note that for a fixed <italic>d</italic>
, if we can solve instance (<italic>l</italic>
,<italic>d</italic>
) we can also solve all instances (<italic>l</italic>
<sup>′</sup>
,<italic>d</italic>
) where <italic>l</italic>
<sup>′</sup>
><italic>l</italic>
, because they are less challenging than (<italic>l</italic>
,<italic>d</italic>
).</p>
</sec>
<sec><title>Appendix 4 Heuristics for t and n</title>
<p>In the methods section we mentioned that we heuristically estimate the threshold <italic>t</italic>
at which we switch from the pattern driven to the sample driven part. The exact formula used by the algorithm to compute <italic>t</italic>
was <inline-formula><mml:math id="M5" name="1471-2105-15-34-i7" overflow="scroll"><mml:mi>t</mml:mi>
<mml:mo>=</mml:mo>
<mml:mo>max</mml:mo>
<mml:mo>(</mml:mo>
<mml:mn>2</mml:mn>
<mml:mo>,</mml:mo>
<mml:mo>⌊</mml:mo>
<mml:msqrt><mml:mrow><mml:mn>2</mml:mn>
<mml:mo>(</mml:mo>
<mml:mi>d</mml:mi>
<mml:mo>+</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>)</mml:mo>
<mml:mo>log</mml:mo>
<mml:mi>Σ</mml:mi>
<mml:mo>-</mml:mo>
<mml:mo>log</mml:mo>
<mml:mi>m</mml:mi>
</mml:mrow>
</mml:msqrt>
<mml:mo>⌋</mml:mo>
<mml:mo>)</mml:mo>
</mml:math>
</inline-formula>
. This follows the intuition that <italic>t</italic>
should increase with <italic>Σ</italic>
to avoid large neighborhoods and decrease with <italic>m</italic>
to avoid spending too much time on filtering.</p>
<p>In the Speedup techniques section we mentioned a speedup where we compute motifs for a subset of <italic>n</italic>
<sup>′</sup>
<<italic>n</italic>
strings. By default, the algorithm heuristically computes <italic>n</italic>
<sup>′</sup>
as <italic>n</italic>
<sup>′</sup>
=<italic>m</italic>
<italic>i</italic>
<italic>n</italic>
(<italic>n</italic>
,<italic>t</italic>
+<italic>n</italic>
/4-<italic>l</italic>
<italic>o</italic>
<italic>g</italic>
<italic>t</italic>
). These simple heuristics worked well enough on all our test cases, however the user can easily override them.</p>
</sec>
</sec>
<sec><title>Competing interests</title>
<p>The authors declare that they have no competing interests.</p>
</sec>
<sec><title>Authors’ contributions</title>
<p>MN and SR designed and analyzed the algorithms. MN implemented the algorithms and carried out the empirical experiments. MN and SR analyzed the empirical results and drafted the manuscript. All authors read and approved the final manuscript.</p>
</sec>
</body>
<back><sec><title>Acknowledgements</title>
<p>The authors would like to thank Prof. Chun-Hsi (Vincent) Huang, Dr. Hieu Dinh, Tian Mi and Gabriel Sebastian Ilie for helpful discussions. This work has been supported in part by the following grants: NSF 0829916 and NIH R01-LM010101.</p>
</sec>
<ref-list><ref id="B1"><mixed-citation publication-type="other"><name><surname>Pevzner</surname>
<given-names>P</given-names>
</name>
<name><surname>Sze</surname>
<given-names>S</given-names>
</name>
<etal></etal>
<article-title>Combinatorial approaches to finding subtle signals in DNA sequences</article-title>
<source>Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, August 19-23, 2000, La Jolla / San Diego, CA, USA, Volume 8</source>
<comment>AAAI 2000:269–278</comment>
</mixed-citation>
</ref>
<ref id="B2"><mixed-citation publication-type="other"><name><surname>Lanctot</surname>
<given-names>J</given-names>
</name>
<name><surname>Li</surname>
<given-names>M</given-names>
</name>
<name><surname>Ma</surname>
<given-names>B</given-names>
</name>
<name><surname>Wang</surname>
<given-names>S</given-names>
</name>
<name><surname>Zhang</surname>
<given-names>L</given-names>
</name>
<article-title>Distinguishing string selection problems</article-title>
<source>Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland</source>
<comment>ACM/SIAM 1999:633–642</comment>
</mixed-citation>
</ref>
<ref id="B3"><mixed-citation publication-type="journal"><name><surname>Yu</surname>
<given-names>Q</given-names>
</name>
<name><surname>Huo</surname>
<given-names>H</given-names>
</name>
<name><surname>Zhang</surname>
<given-names>Y</given-names>
</name>
<name><surname>Guo</surname>
<given-names>H</given-names>
</name>
<article-title>PairMotif: a new pattern-driven algorithm for planted <italic>(l,d)</italic>
DNA motif search</article-title>
<source>PLoS ONE</source>
<year>2012</year>
<volume>7</volume>
<issue>10</issue>
<fpage>e48442</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pone.0048442</pub-id>
<pub-id pub-id-type="pmid">23119020</pub-id>
</mixed-citation>
</ref>
<ref id="B4"><mixed-citation publication-type="journal"><name><surname>Davila</surname>
<given-names>J</given-names>
</name>
<name><surname>Balla</surname>
<given-names>S</given-names>
</name>
<name><surname>Rajasekaran</surname>
<given-names>S</given-names>
</name>
<article-title>Fast and practical algorithms for planted <italic>(l,d)</italic>
motif search</article-title>
<source>IEEE/ACM Trans Comput Biol and Bioinformatics</source>
<year>2007</year>
<volume>4</volume>
<issue>4</issue>
<fpage>544</fpage>
<lpage>552</lpage>
</mixed-citation>
</ref>
<ref id="B5"><mixed-citation publication-type="journal"><name><surname>Dinh</surname>
<given-names>H</given-names>
</name>
<name><surname>Rajasekaran</surname>
<given-names>S</given-names>
</name>
<name><surname>Davila</surname>
<given-names>J</given-names>
</name>
<article-title>qPMS7: A Fast Algorithm for Finding <italic>(l,d)</italic>
-Motifs in DNA and Protein Sequences</article-title>
<source>PLoS ONE</source>
<year>2012</year>
<volume>7</volume>
<issue>7</issue>
<fpage>e41425</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pone.0041425</pub-id>
<pub-id pub-id-type="pmid">22848493</pub-id>
</mixed-citation>
</ref>
<ref id="B6"><mixed-citation publication-type="journal"><name><surname>Ho</surname>
<given-names>E</given-names>
</name>
<name><surname>Jakubowski</surname>
<given-names>C</given-names>
</name>
<name><surname>Gunderson</surname>
<given-names>S</given-names>
</name>
<etal></etal>
<article-title>iTriplet, a rule-based nucleic acid sequence motif finder</article-title>
<source>Algo Mol Biol</source>
<year>2009</year>
<volume>4</volume>
<fpage>14</fpage>
<pub-id pub-id-type="doi">10.1186/1748-7188-4-14</pub-id>
</mixed-citation>
</ref>
<ref id="B7"><mixed-citation publication-type="other"><name><surname>Desaraju</surname>
<given-names>S</given-names>
</name>
<name><surname>Mukkamala</surname>
<given-names>R</given-names>
</name>
<article-title>Multiprocessor implementation of modeling method for Planted Motif Problem</article-title>
<source>2011 World Congress on Information and Communication Technologies (WICT), Dec 11-14, 2011, Mumbai, India</source>
<comment>IEEE 2011:524–529</comment>
</mixed-citation>
</ref>
<ref id="B8"><mixed-citation publication-type="journal"><name><surname>Dinh</surname>
<given-names>H</given-names>
</name>
<name><surname>Rajasekaran</surname>
<given-names>S</given-names>
</name>
<name><surname>Kundeti</surname>
<given-names>V</given-names>
</name>
<article-title>PMS5: an efficient exact algorithm for the <italic>(l,d)</italic>
-motif finding problem</article-title>
<source>BMC Bioinformatics</source>
<year>2011</year>
<volume>12</volume>
<fpage>410</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-12-410</pub-id>
<pub-id pub-id-type="pmid">22024209</pub-id>
</mixed-citation>
</ref>
<ref id="B9"><mixed-citation publication-type="other"><name><surname>Bandyopadhyay</surname>
<given-names>S</given-names>
</name>
<name><surname>Sahni</surname>
<given-names>S</given-names>
</name>
<name><surname>Rajasekaran</surname>
<given-names>S</given-names>
</name>
<article-title>PMS6: A fast algorithm for motif discovery</article-title>
<source>IEEE 2nd International Conference on Computational Advances in Bio and Medical Sciences, ICCABS 2012, Las Vegas, NV, USA, February 23-25, 2012</source>
<comment>IEEE 2012:1–6</comment>
</mixed-citation>
</ref>
<ref id="B10"><mixed-citation publication-type="journal"><name><surname>Rajasekaran</surname>
<given-names>S</given-names>
</name>
<name><surname>Dinh</surname>
<given-names>H</given-names>
</name>
<article-title>A speedup technique for (l, d)-motif finding algorithms</article-title>
<source>BMC Res Notes</source>
<year>2011</year>
<volume>4</volume>
<fpage>54</fpage>
<comment>[<ext-link ext-link-type="uri" xlink:href="http://www.biomedcentral.com/1756-0500/4/54">http://www.biomedcentral.com/1756-0500/4/54</ext-link>
]</comment>
<pub-id pub-id-type="doi">10.1186/1756-0500-4-54</pub-id>
<pub-id pub-id-type="pmid">21385438</pub-id>
</mixed-citation>
</ref>
<ref id="B11"><mixed-citation publication-type="book"><name><surname>Gramm</surname>
<given-names>J</given-names>
</name>
<name><surname>Niedermeier</surname>
<given-names>R</given-names>
</name>
<name><surname>Rossmanith</surname>
<given-names>P</given-names>
</name>
<person-group person-group-type="editor">Eades P, Takaoka T</person-group>
<article-title>Exact solutions for closest string and related problems</article-title>
<source>Algorithms and Computation, Volume 2223 of Lecture Notes in Computer Science</source>
<year>2001</year>
<publisher-name>Berlin Heidelberg: Springer</publisher-name>
<fpage>441</fpage>
<lpage>453</lpage>
</mixed-citation>
</ref>
<ref id="B12"><mixed-citation publication-type="journal"><name><surname>Abbas</surname>
<given-names>M</given-names>
</name>
<name><surname>Abouelhoda</surname>
<given-names>M</given-names>
</name>
<name><surname>Bahig</surname>
<given-names>H</given-names>
</name>
<article-title>A hybrid method for the exact planted (l, d) motif finding problem and its parallelization</article-title>
<source>BMC Bioinformatics</source>
<year>2012</year>
<volume>13</volume>
<issue>Suppl 17</issue>
<fpage>S10</fpage>
<comment>[<ext-link ext-link-type="uri" xlink:href="http://www.biomedcentral.com/1471-2105/13/S17/S10">http://www.biomedcentral.com/1471-2105/13/S17/S10</ext-link>
]</comment>
<pub-id pub-id-type="doi">10.1186/1471-2105-13-S17-S10</pub-id>
<pub-id pub-id-type="pmid">23281969</pub-id>
</mixed-citation>
</ref>
<ref id="B13"><mixed-citation publication-type="book"><name><surname>Dasari</surname>
<given-names>N</given-names>
</name>
<name><surname>Ranjan</surname>
<given-names>D</given-names>
</name>
<name><surname>Zubair</surname>
<given-names>M</given-names>
</name>
<article-title>High performance implementation of planted motif problem using suffix trees</article-title>
<source>2011 International Conference on High Performance Computing & Simulation, HPCS 2012, Istanbul, Turkey, July 4-8, 2011</source>
<year>2011</year>
<publisher-name>IEEE</publisher-name>
<fpage>200</fpage>
<lpage>206</lpage>
</mixed-citation>
</ref>
<ref id="B14"><mixed-citation publication-type="other"><name><surname>Dasari</surname>
<given-names>N</given-names>
</name>
<name><surname>Desh</surname>
<given-names>R</given-names>
</name>
<name><surname>Zubair</surname>
<given-names>M</given-names>
</name>
<article-title>Solving planted motif problem on GPU</article-title>
<source>International Workshop on GPUs and Scientific Applications, GPUScA 2010, Vienna, Austria, September 11, 2010</source>
<comment>Department of Scientific Computing, University of Vienna, TR-10-3 2010</comment>
</mixed-citation>
</ref>
<ref id="B15"><mixed-citation publication-type="other"><name><surname>Dasari</surname>
<given-names>NS</given-names>
</name>
<name><surname>Desh</surname>
<given-names>R</given-names>
</name>
<name><surname>Zubair</surname>
<given-names>M</given-names>
</name>
<article-title>An efficient multicore implementation of planted motif problem</article-title>
<source>Proceedings of the 2010 International Conference on High Performance Computing & Simulation, HPCS 2010, June 28 - July 2, 2010, Caen, France</source>
<comment>IEEE 2010:9 –15</comment>
</mixed-citation>
</ref>
<ref id="B16"><mixed-citation publication-type="journal"><name><surname>Sahoo</surname>
<given-names>B</given-names>
</name>
<name><surname>Sourav</surname>
<given-names>R</given-names>
</name>
<name><surname>Ranjan</surname>
<given-names>R</given-names>
</name>
<name><surname>Padhy</surname>
<given-names>S</given-names>
</name>
<article-title>Parallel implementation of exact algorithm for planted motif search problem using SMP cluster</article-title>
<source>European J Scientific Res</source>
<year>2011</year>
<volume>64</volume>
<issue>4</issue>
<fpage>484</fpage>
<lpage>496</lpage>
</mixed-citation>
</ref>
<ref id="B17"><mixed-citation publication-type="journal"><name><surname>Sun</surname>
<given-names>H</given-names>
</name>
<name><surname>Low</surname>
<given-names>M</given-names>
</name>
<name><surname>Hsu</surname>
<given-names>W</given-names>
</name>
<name><surname>Tan</surname>
<given-names>C</given-names>
</name>
<name><surname>Rajapakse</surname>
<given-names>J</given-names>
</name>
<article-title>Tree-structured algorithm for long weak motif discovery</article-title>
<source>Bioinformatics</source>
<year>2011</year>
<volume>27</volume>
<issue>19</issue>
<fpage>2641</fpage>
<lpage>2647</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btr459</pub-id>
<pub-id pub-id-type="pmid">21821665</pub-id>
</mixed-citation>
</ref>
<ref id="B18"><mixed-citation publication-type="other"><name><surname>Sun</surname>
<given-names>HQ</given-names>
</name>
<name><surname>Low</surname>
<given-names>M</given-names>
</name>
<name><surname>Hsu</surname>
<given-names>WJ</given-names>
</name>
<name><surname>Rajapakse</surname>
<given-names>J</given-names>
</name>
<article-title>ListMotif: A time and memory efficient algorithm for weak motif discovery</article-title>
<source>2010 International Conference on Intelligent Systems and Knowledge Engineering (ISKE), 15-16 November 2010, Hangzhou, China</source>
<comment>IEEE 2010:254 –260</comment>
</mixed-citation>
</ref>
<ref id="B19"><mixed-citation publication-type="other"><name><surname>Faheem</surname>
<given-names>HM</given-names>
</name>
<article-title>Accelerating motif finding problem using grid computing with enhanced brute force</article-title>
<source>Proceedings of the 12th international conference on Advanced communication technology</source>
<comment>ICACT’10, Piscataway, NJ, USA: IEEE Press 2010:197–202</comment>
</mixed-citation>
</ref>
<ref id="B20"><mixed-citation publication-type="journal"><name><surname>Tompa</surname>
<given-names>M</given-names>
</name>
<name><surname>Li</surname>
<given-names>N</given-names>
</name>
<name><surname>Bailey</surname>
<given-names>TL</given-names>
</name>
<name><surname>Church</surname>
<given-names>GM</given-names>
</name>
<name><surname>De Moor</surname>
<given-names>B</given-names>
</name>
<name><surname>Eskin</surname>
<given-names>E</given-names>
</name>
<name><surname>Favorov</surname>
<given-names>AV</given-names>
</name>
<name><surname>Frith</surname>
<given-names>MC</given-names>
</name>
<name><surname>Fu</surname>
<given-names>Y</given-names>
</name>
<name><surname>Kent</surname>
<given-names>WJ</given-names>
</name>
<etal></etal>
<article-title>Assessing computational tools for the discovery of transcription factor binding sites</article-title>
<source>Nature Biotechnol</source>
<year>2005</year>
<volume>23</volume>
<fpage>137</fpage>
<lpage>144</lpage>
<pub-id pub-id-type="doi">10.1038/nbt1053</pub-id>
<pub-id pub-id-type="pmid">15637633</pub-id>
</mixed-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000950 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/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= Corpus |type= RBID |clé= |texte= }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |