A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions
Identifieur interne : 001025 ( Pmc/Corpus ); précédent : 001024; suivant : 001026A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions
Auteurs : Armen Abnousi ; Shira L. Broschat ; Ananth KalyanaramanSource :
- PLoS ONE [ 1932-6203 ] ; 2016.
Abstract
Identifying conserved regions in protein sequences is a fundamental operation, occurring in numerous sequence-driven analysis pipelines. It is used as a way to decode domain-rich regions within proteins, to compute protein clusters, to annotate sequence function, and to compute evolutionary relationships among protein sequences. A number of approaches exist for identifying and characterizing protein families based on their domains, and because domains represent conserved portions of a protein sequence, the primary computation involved in protein family characterization is identification of such conserved regions. However, identifying conserved regions from large collections (millions) of protein sequences presents significant challenges.
In this paper we present a new, alignment-free method for detecting conserved regions in protein sequences called NADDA (No-Alignment Domain Detection Algorithm). Our method exploits the abundance of exact matching short subsequences (
We have compared NADDA with Pfam and InterPro databases. For known domains annotated by Pfam, accuracy is 83%, sensitivity 96%, and specificity 44%. For sequences with new domains not present in the training set an average accuracy of 63% is achieved when compared to Pfam. A boost in results in comparison with InterPro demonstrates the ability of NADDA to capture conserved regions beyond those present in Pfam. We have also compared NADDA with ADDA and MKDOM2, assuming Pfam as ground-truth. On average NADDA shows comparable accuracy, more balanced sensitivity and specificity, and being alignment-free, is significantly faster. Excluding the one-time cost of training, runtimes on a single processor were 49s, 10,566s, and 456s for NADDA, ADDA, and MKDOM2, respectively, for a data set comprised of approximately 2500 sequences.
Url:
DOI: 10.1371/journal.pone.0161338
PubMed: 27552220
PubMed Central: 4995020
Links to Exploration step
PMC:4995020Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions</title>
<author><name sortKey="Abnousi, Armen" sort="Abnousi, Armen" uniqKey="Abnousi A" first="Armen" last="Abnousi">Armen Abnousi</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Broschat, Shira L" sort="Broschat, Shira L" uniqKey="Broschat S" first="Shira L." last="Broschat">Shira L. Broschat</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff002"><addr-line>Paul G. Allen School for Global Animal Health, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff003"><addr-line>Department of Veterinary Microbiology and Pathology, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Kalyanaraman, Ananth" sort="Kalyanaraman, Ananth" uniqKey="Kalyanaraman A" first="Ananth" last="Kalyanaraman">Ananth Kalyanaraman</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff002"><addr-line>Paul G. Allen School for Global Animal Health, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">27552220</idno>
<idno type="pmc">4995020</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4995020</idno>
<idno type="RBID">PMC:4995020</idno>
<idno type="doi">10.1371/journal.pone.0161338</idno>
<date when="2016">2016</date>
<idno type="wicri:Area/Pmc/Corpus">001025</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">001025</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions</title>
<author><name sortKey="Abnousi, Armen" sort="Abnousi, Armen" uniqKey="Abnousi A" first="Armen" last="Abnousi">Armen Abnousi</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Broschat, Shira L" sort="Broschat, Shira L" uniqKey="Broschat S" first="Shira L." last="Broschat">Shira L. Broschat</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff002"><addr-line>Paul G. Allen School for Global Animal Health, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff003"><addr-line>Department of Veterinary Microbiology and Pathology, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Kalyanaraman, Ananth" sort="Kalyanaraman, Ananth" uniqKey="Kalyanaraman A" first="Ananth" last="Kalyanaraman">Ananth Kalyanaraman</name>
<affiliation><nlm:aff id="aff001"><addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff002"><addr-line>Paul G. Allen School for Global Animal Health, Washington State University, Pullman, WA, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">PLoS ONE</title>
<idno type="eISSN">1932-6203</idno>
<imprint><date when="2016">2016</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec id="sec001"><title>Background</title>
<p>Identifying conserved regions in protein sequences is a fundamental operation, occurring in numerous sequence-driven analysis pipelines. It is used as a way to decode domain-rich regions within proteins, to compute protein clusters, to annotate sequence function, and to compute evolutionary relationships among protein sequences. A number of approaches exist for identifying and characterizing protein families based on their domains, and because domains represent conserved portions of a protein sequence, the primary computation involved in protein family characterization is identification of such conserved regions. However, identifying conserved regions from large collections (millions) of protein sequences presents significant challenges.</p>
</sec>
<sec id="sec002"><title>Methods</title>
<p>In this paper we present a new, alignment-free method for detecting conserved regions in protein sequences called NADDA (No-Alignment Domain Detection Algorithm). Our method exploits the abundance of exact matching short subsequences (<italic>k</italic>
-mers) to quickly detect conserved regions, and the power of machine learning is used to improve the prediction accuracy of detection. We present a parallel implementation of NADDA using the MapReduce framework and show that our method is highly scalable.</p>
</sec>
<sec id="sec003"><title>Results</title>
<p>We have compared NADDA with Pfam and InterPro databases. For known domains annotated by Pfam, accuracy is 83%, sensitivity 96%, and specificity 44%. For sequences with new domains not present in the training set an average accuracy of 63% is achieved when compared to Pfam. A boost in results in comparison with InterPro demonstrates the ability of NADDA to capture conserved regions beyond those present in Pfam. We have also compared NADDA with ADDA and MKDOM2, assuming Pfam as ground-truth. On average NADDA shows comparable accuracy, more balanced sensitivity and specificity, and being alignment-free, is significantly faster. Excluding the one-time cost of training, runtimes on a single processor were 49s, 10,566s, and 456s for NADDA, ADDA, and MKDOM2, respectively, for a data set comprised of approximately 2500 sequences.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Consortium, U" uniqKey="Consortium U">U Consortium</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Doolittle, Rf" uniqKey="Doolittle R">RF Doolittle</name>
</author>
<author><name sortKey="Bork, P" uniqKey="Bork P">P Bork</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Heger, A" uniqKey="Heger A">A Heger</name>
</author>
<author><name sortKey="Holm, L" uniqKey="Holm L">L Holm</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Portugaly, E" uniqKey="Portugaly E">E Portugaly</name>
</author>
<author><name sortKey="Harel, A" uniqKey="Harel A">A Harel</name>
</author>
<author><name sortKey="Linial, N" uniqKey="Linial N">N Linial</name>
</author>
<author><name sortKey="Linial, M" uniqKey="Linial M">M Linial</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gouzy, J" uniqKey="Gouzy J">J Gouzy</name>
</author>
<author><name sortKey="Corpet, F" uniqKey="Corpet F">F Corpet</name>
</author>
<author><name sortKey="Kahn, D" uniqKey="Kahn D">D Kahn</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Tress, M" uniqKey="Tress M">M Tress</name>
</author>
<author><name sortKey="Cheng, J" uniqKey="Cheng J">J Cheng</name>
</author>
<author><name sortKey="Baldi, P" uniqKey="Baldi P">P Baldi</name>
</author>
<author><name sortKey="Joo, K" uniqKey="Joo K">K Joo</name>
</author>
<author><name sortKey="Lee, J" uniqKey="Lee J">J Lee</name>
</author>
<author><name sortKey="Seo, Jh" uniqKey="Seo J">JH Seo</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tai, Ch" uniqKey="Tai C">CH Tai</name>
</author>
<author><name sortKey="Lee, Wj" uniqKey="Lee W">WJ Lee</name>
</author>
<author><name sortKey="Vincent, Jj" uniqKey="Vincent J">JJ Vincent</name>
</author>
<author><name sortKey="Lee, B" uniqKey="Lee B">B Lee</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Eickholt, J" uniqKey="Eickholt J">J Eickholt</name>
</author>
<author><name sortKey="Deng, X" uniqKey="Deng X">X Deng</name>
</author>
<author><name sortKey="Cheng, J" uniqKey="Cheng J">J Cheng</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name>
</author>
<author><name sortKey="Madden, Tl" uniqKey="Madden T">TL Madden</name>
</author>
<author><name sortKey="Sch Ffer, Aa" uniqKey="Sch Ffer A">AA Schäffer</name>
</author>
<author><name sortKey="Zhang, J" uniqKey="Zhang J">J Zhang</name>
</author>
<author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gouzy, J" uniqKey="Gouzy J">J Gouzy</name>
</author>
<author><name sortKey="Eugene, P" uniqKey="Eugene P">P Eugene</name>
</author>
<author><name sortKey="Greene, Ea" uniqKey="Greene E">EA Greene</name>
</author>
<author><name sortKey="Kahn, D" uniqKey="Kahn D">D Kahn</name>
</author>
<author><name sortKey="Corpet, F" uniqKey="Corpet F">F Corpet</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sonnhammer, El" uniqKey="Sonnhammer E">EL Sonnhammer</name>
</author>
<author><name sortKey="Kahn, D" uniqKey="Kahn D">D Kahn</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bru, C" uniqKey="Bru C">C Bru</name>
</author>
<author><name sortKey="Courcelle, E" uniqKey="Courcelle E">E Courcelle</name>
</author>
<author><name sortKey="Carrere, S" uniqKey="Carrere S">S Carrère</name>
</author>
<author><name sortKey="Beausse, Y" uniqKey="Beausse Y">Y Beausse</name>
</author>
<author><name sortKey="Dalmar, S" uniqKey="Dalmar S">S Dalmar</name>
</author>
<author><name sortKey="Kahn, D" uniqKey="Kahn D">D Kahn</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name>
</author>
<author><name sortKey="Gish, W" uniqKey="Gish W">W Gish</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
<author><name sortKey="Myers, Ew" uniqKey="Myers E">EW Myers</name>
</author>
<author><name sortKey="Lipman, Dj" uniqKey="Lipman D">DJ Lipman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Smith, Tf" uniqKey="Smith T">TF Smith</name>
</author>
<author><name sortKey="Waterman, Ms" uniqKey="Waterman M">MS Waterman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dean, J" uniqKey="Dean J">J Dean</name>
</author>
<author><name sortKey="Ghemawat, S" uniqKey="Ghemawat S">S Ghemawat</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Breiman, L" uniqKey="Breiman L">L Breiman</name>
</author>
<author><name sortKey="Friedman, Jh" uniqKey="Friedman J">JH Friedman</name>
</author>
<author><name sortKey="Olshen, Ra" uniqKey="Olshen R">RA Olshen</name>
</author>
<author><name sortKey="Stone, Cj" uniqKey="Stone C">CJ Stone</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Quilan, J" uniqKey="Quilan J">J Quilan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ho, Tk" uniqKey="Ho T">TK Ho</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Plimpton, Sj" uniqKey="Plimpton S">SJ Plimpton</name>
</author>
<author><name sortKey="Devine, Kd" uniqKey="Devine K">KD Devine</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pedregosa, F" uniqKey="Pedregosa F">F Pedregosa</name>
</author>
<author><name sortKey="Varoquaux, G" uniqKey="Varoquaux G">G Varoquaux</name>
</author>
<author><name sortKey="Gramfort, A" uniqKey="Gramfort A">A Gramfort</name>
</author>
<author><name sortKey="Michel, V" uniqKey="Michel V">V Michel</name>
</author>
<author><name sortKey="Thirion, B" uniqKey="Thirion B">B Thirion</name>
</author>
<author><name sortKey="Grisel, O" uniqKey="Grisel O">O Grisel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Jones, P" uniqKey="Jones P">P Jones</name>
</author>
<author><name sortKey="Binns, D" uniqKey="Binns D">D Binns</name>
</author>
<author><name sortKey="Chang, Hy" uniqKey="Chang H">HY Chang</name>
</author>
<author><name sortKey="Fraser, M" uniqKey="Fraser M">M Fraser</name>
</author>
<author><name sortKey="Li, W" uniqKey="Li W">W Li</name>
</author>
<author><name sortKey="Mcanulla, C" uniqKey="Mcanulla C">C McAnulla</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schultz, J" uniqKey="Schultz J">J Schultz</name>
</author>
<author><name sortKey="Milpetz, F" uniqKey="Milpetz F">F Milpetz</name>
</author>
<author><name sortKey="Bork, P" uniqKey="Bork P">P Bork</name>
</author>
<author><name sortKey="Ponting, Cp" uniqKey="Ponting C">CP Ponting</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Finn, Rd" uniqKey="Finn R">RD Finn</name>
</author>
<author><name sortKey="Coggill, P" uniqKey="Coggill P">P Coggill</name>
</author>
<author><name sortKey="Eberhardt, Ry" uniqKey="Eberhardt R">RY Eberhardt</name>
</author>
<author><name sortKey="Eddy, Sr" uniqKey="Eddy S">SR Eddy</name>
</author>
<author><name sortKey="Mistry, J" uniqKey="Mistry J">J Mistry</name>
</author>
<author><name sortKey="Mitchell, Al" uniqKey="Mitchell A">AL Mitchell</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sigrist, Cj" uniqKey="Sigrist C">CJ Sigrist</name>
</author>
<author><name sortKey="De Castro, E" uniqKey="De Castro E">E De Castro</name>
</author>
<author><name sortKey="Cerutti, L" uniqKey="Cerutti L">L Cerutti</name>
</author>
<author><name sortKey="Cuche, Ba" uniqKey="Cuche B">BA Cuche</name>
</author>
<author><name sortKey="Hulo, N" uniqKey="Hulo N">N Hulo</name>
</author>
<author><name sortKey="Bridge, A" uniqKey="Bridge A">A Bridge</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Haft, Dh" uniqKey="Haft D">DH Haft</name>
</author>
<author><name sortKey="Selengut, Jd" uniqKey="Selengut J">JD Selengut</name>
</author>
<author><name sortKey="Richter, Ra" uniqKey="Richter R">RA Richter</name>
</author>
<author><name sortKey="Harkins, D" uniqKey="Harkins D">D Harkins</name>
</author>
<author><name sortKey="Basu, Mk" uniqKey="Basu M">MK Basu</name>
</author>
<author><name sortKey="Beck, E" uniqKey="Beck E">E Beck</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Srivastava, A" uniqKey="Srivastava A">A Srivastava</name>
</author>
<author><name sortKey="Han, Eh" uniqKey="Han E">EH Han</name>
</author>
<author><name sortKey="Kumar, V" uniqKey="Kumar V">V Kumar</name>
</author>
<author><name sortKey="Singh, V" uniqKey="Singh V">V Singh</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">PLoS One</journal-id>
<journal-id journal-id-type="iso-abbrev">PLoS ONE</journal-id>
<journal-id journal-id-type="publisher-id">plos</journal-id>
<journal-id journal-id-type="pmc">plosone</journal-id>
<journal-title-group><journal-title>PLoS ONE</journal-title>
</journal-title-group>
<issn pub-type="epub">1932-6203</issn>
<publisher><publisher-name>Public Library of Science</publisher-name>
<publisher-loc>San Francisco, CA USA</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">27552220</article-id>
<article-id pub-id-type="pmc">4995020</article-id>
<article-id pub-id-type="publisher-id">PONE-D-16-08725</article-id>
<article-id pub-id-type="doi">10.1371/journal.pone.0161338</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Biology and Life Sciences</subject>
<subj-group><subject>Biochemistry</subject>
<subj-group><subject>Proteins</subject>
<subj-group><subject>Protein Domains</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Biology and Life Sciences</subject>
<subj-group><subject>Molecular Biology</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Alignment</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Alignment</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Database and Informatics Methods</subject>
<subj-group><subject>Biological Databases</subject>
<subj-group><subject>Sequence Databases</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Biology and Life Sciences</subject>
<subj-group><subject>Molecular Biology</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Databases</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Databases</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Physical Sciences</subject>
<subj-group><subject>Mathematics</subject>
<subj-group><subject>Applied Mathematics</subject>
<subj-group><subject>Algorithms</subject>
<subj-group><subject>Machine Learning Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Simulation and Modeling</subject>
<subj-group><subject>Algorithms</subject>
<subj-group><subject>Machine Learning Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Biology and Life Sciences</subject>
<subj-group><subject>Neuroscience</subject>
<subj-group><subject>Cognitive Science</subject>
<subj-group><subject>Artificial Intelligence</subject>
<subj-group><subject>Machine Learning</subject>
<subj-group><subject>Machine Learning Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Computer and Information Sciences</subject>
<subj-group><subject>Artificial Intelligence</subject>
<subj-group><subject>Machine Learning</subject>
<subj-group><subject>Machine Learning Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Biology and Life Sciences</subject>
<subj-group><subject>Molecular Biology</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Motif Analysis</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Molecular Biology Techniques</subject>
<subj-group><subject>Sequencing Techniques</subject>
<subj-group><subject>Sequence Analysis</subject>
<subj-group><subject>Sequence Motif Analysis</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Physical Sciences</subject>
<subj-group><subject>Mathematics</subject>
<subj-group><subject>Applied Mathematics</subject>
<subj-group><subject>Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Simulation and Modeling</subject>
<subj-group><subject>Algorithms</subject>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Physical sciences</subject>
<subj-group><subject>Mathematics</subject>
<subj-group><subject>Applied mathematics</subject>
<subj-group><subject>Algorithms</subject>
<subj-group><subject>BLAST algorithm</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and analysis methods</subject>
<subj-group><subject>Simulation and modeling</subject>
<subj-group><subject>Algorithms</subject>
<subj-group><subject>BLAST algorithm</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and analysis methods</subject>
<subj-group><subject>Database and informatics methods</subject>
<subj-group><subject>Bioinformatics</subject>
<subj-group><subject>Software-aided sequence analysis</subject>
<subj-group><subject>BLAST algorithm</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Engineering and Technology</subject>
<subj-group><subject>Management Engineering</subject>
<subj-group><subject>Decision Analysis</subject>
<subj-group><subject>Decision Trees</subject>
</subj-group>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v3"><subject>Research and Analysis Methods</subject>
<subj-group><subject>Decision Analysis</subject>
<subj-group><subject>Decision Trees</subject>
</subj-group>
</subj-group>
</subj-group>
</article-categories>
<title-group><article-title>A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions</article-title>
<alt-title alt-title-type="running-head">NADDA: Alignment-Free Detection of Protein Conserved Regions</alt-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Abnousi</surname>
<given-names>Armen</given-names>
</name>
<xref ref-type="aff" rid="aff001"><sup>1</sup>
</xref>
<xref ref-type="corresp" rid="cor001">*</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Broschat</surname>
<given-names>Shira L.</given-names>
</name>
<xref ref-type="aff" rid="aff001"><sup>1</sup>
</xref>
<xref ref-type="aff" rid="aff002"><sup>2</sup>
</xref>
<xref ref-type="aff" rid="aff003"><sup>3</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Kalyanaraman</surname>
<given-names>Ananth</given-names>
</name>
<xref ref-type="aff" rid="aff001"><sup>1</sup>
</xref>
<xref ref-type="aff" rid="aff002"><sup>2</sup>
</xref>
</contrib>
</contrib-group>
<aff id="aff001"><label>1</label>
<addr-line>School of EECS, Washington State University, Pullman, WA, United States of America</addr-line>
</aff>
<aff id="aff002"><label>2</label>
<addr-line>Paul G. Allen School for Global Animal Health, Washington State University, Pullman, WA, United States of America</addr-line>
</aff>
<aff id="aff003"><label>3</label>
<addr-line>Department of Veterinary Microbiology and Pathology, Washington State University, Pullman, WA, United States of America</addr-line>
</aff>
<contrib-group><contrib contrib-type="editor"><name><surname>Zhang</surname>
<given-names>Yang</given-names>
</name>
<role>Editor</role>
<xref ref-type="aff" rid="edit1"></xref>
</contrib>
</contrib-group>
<aff id="edit1"><addr-line>University of Michigan, UNITED STATES</addr-line>
</aff>
<author-notes><fn fn-type="COI-statement" id="coi001"><p><bold>Competing Interests: </bold>
The authors have declared that no competing interests exist.</p>
</fn>
<fn fn-type="con"><p><list list-type="simple"><list-item><p><bold>Conceptualization:</bold>
AK.</p>
</list-item>
<list-item><p><bold>Formal analysis:</bold>
AA.</p>
</list-item>
<list-item><p><bold>Funding acquisition:</bold>
SLB AK.</p>
</list-item>
<list-item><p><bold>Investigation:</bold>
AA.</p>
</list-item>
<list-item><p><bold>Methodology:</bold>
AA AK.</p>
</list-item>
<list-item><p><bold>Project administration:</bold>
SLB AK.</p>
</list-item>
<list-item><p><bold>Resources:</bold>
AK.</p>
</list-item>
<list-item><p><bold>Software:</bold>
AA.</p>
</list-item>
<list-item><p><bold>Supervision:</bold>
AK SLB.</p>
</list-item>
<list-item><p><bold>Validation:</bold>
AA.</p>
</list-item>
<list-item><p><bold>Visualization:</bold>
AA AK SLB.</p>
</list-item>
<list-item><p><bold>Writing – original draft:</bold>
AA.</p>
</list-item>
<list-item><p><bold>Writing – review & editing:</bold>
AA AK SLB.</p>
</list-item>
</list>
</p>
</fn>
<corresp id="cor001">* E-mail: <email>aabnousi@eecs.wsu.edu</email>
</corresp>
</author-notes>
<pub-date pub-type="collection"><year>2016</year>
</pub-date>
<pub-date pub-type="epub"><day>23</day>
<month>8</month>
<year>2016</year>
</pub-date>
<volume>11</volume>
<issue>8</issue>
<elocation-id>e0161338</elocation-id>
<history><date date-type="received"><day>29</day>
<month>2</month>
<year>2016</year>
</date>
<date date-type="accepted"><day>3</day>
<month>8</month>
<year>2016</year>
</date>
</history>
<permissions><copyright-statement>© 2016 Abnousi et al</copyright-statement>
<copyright-year>2016</copyright-year>
<copyright-holder>Abnousi et al</copyright-holder>
<license xlink:href="http://creativecommons.org/licenses/by/4.0/"><license-p>This is an open access article distributed under the terms of the <ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution License</ext-link>
, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.</license-p>
</license>
</permissions>
<self-uri content-type="pdf" xlink:href="pone.0161338.pdf"></self-uri>
<abstract><sec id="sec001"><title>Background</title>
<p>Identifying conserved regions in protein sequences is a fundamental operation, occurring in numerous sequence-driven analysis pipelines. It is used as a way to decode domain-rich regions within proteins, to compute protein clusters, to annotate sequence function, and to compute evolutionary relationships among protein sequences. A number of approaches exist for identifying and characterizing protein families based on their domains, and because domains represent conserved portions of a protein sequence, the primary computation involved in protein family characterization is identification of such conserved regions. However, identifying conserved regions from large collections (millions) of protein sequences presents significant challenges.</p>
</sec>
<sec id="sec002"><title>Methods</title>
<p>In this paper we present a new, alignment-free method for detecting conserved regions in protein sequences called NADDA (No-Alignment Domain Detection Algorithm). Our method exploits the abundance of exact matching short subsequences (<italic>k</italic>
-mers) to quickly detect conserved regions, and the power of machine learning is used to improve the prediction accuracy of detection. We present a parallel implementation of NADDA using the MapReduce framework and show that our method is highly scalable.</p>
</sec>
<sec id="sec003"><title>Results</title>
<p>We have compared NADDA with Pfam and InterPro databases. For known domains annotated by Pfam, accuracy is 83%, sensitivity 96%, and specificity 44%. For sequences with new domains not present in the training set an average accuracy of 63% is achieved when compared to Pfam. A boost in results in comparison with InterPro demonstrates the ability of NADDA to capture conserved regions beyond those present in Pfam. We have also compared NADDA with ADDA and MKDOM2, assuming Pfam as ground-truth. On average NADDA shows comparable accuracy, more balanced sensitivity and specificity, and being alignment-free, is significantly faster. Excluding the one-time cost of training, runtimes on a single processor were 49s, 10,566s, and 456s for NADDA, ADDA, and MKDOM2, respectively, for a data set comprised of approximately 2500 sequences.</p>
</sec>
</abstract>
<funding-group><award-group id="award001"><funding-source><institution>National Science Foundation (US)</institution>
</funding-source>
<award-id>1262664</award-id>
<principal-award-recipient><name><surname>Broschat</surname>
<given-names>Shira L</given-names>
</name>
</principal-award-recipient>
</award-group>
<funding-statement>This work was funded by support from the National Science Foundation under the Advances in Biological Informatics program (NSF ABI), Award #1262664 (URL: <ext-link ext-link-type="uri" xlink:href="http://nsf.gov/awardsearch/showAward?AWD_ID=1262664&HistoricalAwards=false">http://nsf.gov/awardsearch/showAward?AWD_ID=1262664&HistoricalAwards=false</ext-link>
). Award is received by SLB and AK. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.</funding-statement>
</funding-group>
<counts><fig-count count="4"></fig-count>
<table-count count="15"></table-count>
<page-count count="19"></page-count>
</counts>
<custom-meta-group><custom-meta id="data-availability"><meta-name>Data Availability</meta-name>
<meta-value>All the data used in this paper were taken from the following online public databases: Pfam (<ext-link ext-link-type="uri" xlink:href="http://pfam.xfam.org/">http://pfam.xfam.org/</ext-link>
) and SMART (<ext-link ext-link-type="uri" xlink:href="http://smart.embl-heidelberg.de/">http://smart.embl-heidelberg.de/</ext-link>
). Details about the accession numbers and procedure to retrieve the data sets are provided in the paper.</meta-value>
</custom-meta>
</custom-meta-group>
</article-meta>
<notes><title>Data Availability</title>
<p>All the data used in this paper were taken from the following online public databases: Pfam (<ext-link ext-link-type="uri" xlink:href="http://pfam.xfam.org/">http://pfam.xfam.org/</ext-link>
) and SMART (<ext-link ext-link-type="uri" xlink:href="http://smart.embl-heidelberg.de/">http://smart.embl-heidelberg.de/</ext-link>
). Details about the accession numbers and procedure to retrieve the data sets are provided in the paper.</p>
</notes>
</front>
<body><sec sec-type="intro" id="sec004"><title>Introduction</title>
<p>Proteins play a vital role in living organisms. They are the main players in metabolic pathways, and to understand how cells work requires insight into the structure and knowledge of the function of a protein. A plethora of research to determine the structure and function of proteins has been conducted, but the rate of knowledge generated has grown much more slowly than the universe of identified proteins has. For example, between two releases of the UniProt Knowledgebase [<xref rid="pone.0161338.ref001" ref-type="bibr">1</xref>
] (from release 2015_11 to 2015_12) only 287 sequences were added to the Swissprot section, which contains curated protein sequences with high levels of annotation. Over the same time period, the TrEMBL section (for automatically annotated sequences) has been augmented with more than 590,000 protein sequences. The need for more accurate and scalable automatic methods is compelling.</p>
<p>Variation in proteins comes from recombination and mutations in evolutionary modules [<xref rid="pone.0161338.ref002" ref-type="bibr">2</xref>
]. These modules are generally known as <italic>domains</italic>
. A single protein is made up of one or more domains. Thus, the detection of domains of protein sequences can be regarded as the initial step in domain family identification and protein clustering, which in turn can help in function and structure assignments. Accurate annotation of conserved regions, as building blocks of protein sequences, can also contribute to construction of evolutionary trees.</p>
<p>Many current approaches perform the detection of sequence domains by detecting only putative regions and as a part of domain family identification, i.e., protein clustering based on domains rather than as a separate question [<xref rid="pone.0161338.ref003" ref-type="bibr">3</xref>
–<xref rid="pone.0161338.ref005" ref-type="bibr">5</xref>
]. To the best of our knowledge there is no published research concentrating only on detecting conserved regions in proteins. Although correlation between the detection of domain regions and clustering based on domains appears to be natural, one can argue that a cluster is a global property of the universe of proteins, but a domain is a local property of each sequence which, as the definition suggests, needs to be common to many sequences. Global approaches to domain family identification also often involve the expensive operation of sequence alignment. Hence, fast and accurate detection of domain regions will contribute to the global operation of clustering proteins, both by improving the accuracy of detection and reducing runtime by removing expensive sequence alignment operations.</p>
<p>While the unprecedented growth in numbers of sequenced proteins has been a challenge for integration of automated methods in proteomics, the abundance of sequences also presents us with an opportunity: as the number of protein sequences containing domains increases, the frequency of occurrence of a particular domain also increases, making it easier to detect. Our task, then, is to extract high frequency regions from within the protein sequences. As we explain fully below, for each sequence, our alignment-free method translates its level of similarity to other sequences into a vector and then looks through each vector to detect the pattern within its indices. While we introduced the idea of this translation into a vector in [<xref rid="pone.0161338.ref006" ref-type="bibr">6</xref>
], our experiments showed that our simple mathematical approach resulted in a heavy inter-dependence between the parameters selected for the method and the protein sequences. Here, we improve upon this previous work [<xref rid="pone.0161338.ref006" ref-type="bibr">6</xref>
] by integrating a machine learning approach that reduces the dependence on parameters while improving the accuracy. We have also augmented our work with an extensive experimental results section in which we not only validate our proposed method but also provide comparison of our results with the results of other existing methods.</p>
<sec id="sec005"><title>Related Work</title>
<p>While detection of structural domains as opposed to functional domains has been an area of active research featured as a part of CASP experiments [<xref rid="pone.0161338.ref007" ref-type="bibr">7</xref>
–<xref rid="pone.0161338.ref009" ref-type="bibr">9</xref>
], the detection of sequence level conserved regions has been mostly overshadowed by efforts to cluster proteins based on their domain families [<xref rid="pone.0161338.ref003" ref-type="bibr">3</xref>
–<xref rid="pone.0161338.ref005" ref-type="bibr">5</xref>
]. In MKDOM2 [<xref rid="pone.0161338.ref005" ref-type="bibr">5</xref>
], the shortest sequence (without repetitions) is marked as a domain and then PSI-BLAST [<xref rid="pone.0161338.ref010" ref-type="bibr">10</xref>
] is used to detect regions of high similarity with that domain. Sequences containing regions similar to that domain are put in one cluster. The detected sections are removed from the sequences and the same operation is repeated to find other domains. The objective of MKDOM2 is expressed as identification of domain families rather than detection of domain regions themselves. MKDOM2 is an improvement over MKDOM [<xref rid="pone.0161338.ref011" ref-type="bibr">11</xref>
] which in turn succeeded DOMAINER [<xref rid="pone.0161338.ref012" ref-type="bibr">12</xref>
]. All three have been used to generate the ProDom protein family database [<xref rid="pone.0161338.ref013" ref-type="bibr">13</xref>
]. Parallelization of MKDOM2 has been implemented using a master-worker structure [<xref rid="pone.0161338.ref014" ref-type="bibr">14</xref>
].</p>
<p>In ADDA [<xref rid="pone.0161338.ref003" ref-type="bibr">3</xref>
], an all vs. all BLAST [<xref rid="pone.0161338.ref015" ref-type="bibr">15</xref>
] is performed on the entire data set. Based on the results of BLAST, a tree of putative domain regions is generated for each sequence. An optimization target is then used to find the final partitioning for each sequence. Unification is performed to construct a new graph based on final partitions and to cluster similar proteins together. In ADDA, domain boundary assessments are performed using the trees of putative domains. However, the final goal being domain family enumeration, unification is a crucial step and can possibly improve the partitions. An implementation of construction of ADDA putative domain trees of protein sequences from their all vs. all BLAST results has also been presented with support for parallel/multi-threaded executions.</p>
<p>In EVEREST [<xref rid="pone.0161338.ref004" ref-type="bibr">4</xref>
] an all vs. all BLAST on the data set is followed by runs of the Smith-Waterman algorithm [<xref rid="pone.0161338.ref016" ref-type="bibr">16</xref>
] on the selected sequences to generate a set of putative domain regions. After applying a series of different methods, including clustering the sequences based on detected putative domain regions, filtering low-scoring clusters using a boosting machine learning technique, and profile construction using ClustalW for each cluster, EVEREST finds a set of HMM profiles. The segments detected by these profiles replace the initial putative domain list and correspond to suggested domain families. This operation is repeated iteratively.</p>
<p>As can be seen, all three of these approaches focus on domain family identification rather than domain region detection, but they also use some methods for detection of putative domain regions as a preliminary operation for their final objective.</p>
<p>In this paper we present NADDA (No-Alignment Domain Detection Algorithm), an alignment-free, scalable method for detection of conserved regions in proteins. In the next section we present our approach to the problem. In the Results section we evaluate our method and compare its results with other methods. We conclude the paper by a brief discussion on what we achieved and prospective future work.</p>
</sec>
</sec>
<sec sec-type="materials|methods" id="sec006"><title>Methods</title>
<p>Given a set <italic>S</italic>
of <italic>n</italic>
sequences, the problem of <italic>conserved region detection</italic>
of protein sequences can be expressed as the demarcation of subsequences in each of the <italic>n</italic>
sequences such that these subsequences are preserved over the evolutionary process. The preservation of these subsequences can be identified by a high local similarity score when the protein is aligned with other proteins of the same family. These conserved subsequences appear as motifs and sequence domains. Our method uses the frequency of short exact matching subsequences (<italic>k</italic>
-mers) of a protein sequence in the data set as an indicator of the existence of a conserved region in the vicinity of that <italic>k</italic>
-mer.</p>
<p><bold>Problem Definition:</bold>
</p>
<p><bold>Notation:</bold>
Given a sequence <italic>s</italic>
, we denote the <italic>i</italic>
<sup><italic>th</italic>
</sup>
character of <italic>s</italic>
by <italic>s</italic>
[<italic>i</italic>
] and the substring of length <italic>l</italic>
that starts at index <italic>i</italic>
of <italic>s</italic>
by <italic>s</italic>
(<italic>i</italic>
, <italic>l</italic>
). We denote the length of a sequence <italic>s</italic>
by |<italic>s</italic>
|. A <italic>k</italic>
-mer is a string of length <italic>k</italic>
.</p>
<p>Additionally, let <italic>S</italic>
= {<italic>s</italic>
<sub>1</sub>
, <italic>s</italic>
<sub>2</sub>
, …, <italic>s</italic>
<sub><italic>n</italic>
</sub>
} denote an input set of <italic>n</italic>
protein sequences. We define:</p>
<p><bold>Definition 1</bold>
<italic>k</italic>
-mer frequency: <italic>The</italic>
frequency <italic>of a k-mer in S is defined as the number of sequences in S that contain that k-mer at least once</italic>
.</p>
<p>A conserved window is then a substring of length <italic>r</italic>
, centered at index <italic>i</italic>
, where the average frequencies of <italic>k</italic>
-mers in that substring is above a certain threshold <italic>τ</italic>
. However, this definition is heavily dependent on the values of the threshold (<italic>τ</italic>
) and the window size (<italic>r</italic>
). To compensate for these limitations, we consider a smaller resolution of regions—indices. For each index <italic>i</italic>
we consider a window of size 2 × <italic>w</italic>
+ 1 centered at <italic>i</italic>
, and based on the frequency of <italic>k</italic>
-mers inside this window we decide whether or not index <italic>i</italic>
is part of a conserved region. The decision based on <italic>k</italic>
-mer frequencies is not dependent on a single threshold <italic>τ</italic>
; rather we find a set of thresholds {<italic>τ</italic>
<sub>1</sub>
, <italic>τ</italic>
<sub>2</sub>
, …, <italic>τ</italic>
<sub>2×<italic>w</italic>
+1</sub>
} where <italic>τ</italic>
<sub><italic>j</italic>
</sub>
is used as a threshold for the <italic>j</italic>
<sup><italic>th</italic>
</sup>
<italic>k</italic>
-mer in the window, i.e., the <italic>k</italic>
-mer originating at index <italic>i</italic>
− <italic>w</italic>
+ <italic>j</italic>
− 1 of the sequence. This set of thresholds is found using our machine learning algorithm, and the prediction is also made by a combination of comparisons based on the thresholds.</p>
<p><bold>Definition 2</bold>
Conserved Region: <italic>Given a sequence s ∈ S, a substring s(i, l) is said to be a</italic>
conserved region <italic>if</italic>
:</p>
<list list-type="order"><list-item><p><italic>(conservation) every</italic>
<italic>s</italic>
[<italic>j</italic>
] <italic>for</italic>
<italic>j</italic>
∈ [<italic>i</italic>
, <italic>i</italic>
+ <italic>l</italic>
] <italic>is a conserved index, and</italic>
</p>
</list-item>
<list-item><p><italic>(maximality) neither the index</italic>
<italic>s</italic>
[<italic>i</italic>
− 1] <italic>nor the index</italic>
<italic>s</italic>
[<italic>i</italic>
+ <italic>l</italic>
+ 1] <italic>(if either exists) is a conserved index</italic>
.</p>
</list-item>
</list>
<p>From the problem definition above, a simple approach is to compare each pair of sequences (<inline-formula id="pone.0161338.e001"><alternatives><graphic xlink:href="pone.0161338.e001.jpg" id="pone.0161338.e001g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M1"><mml:mrow><mml:mrow><mml:mo>(</mml:mo>
<mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mi>n</mml:mi>
</mml:mtd>
</mml:mtr>
<mml:mtr><mml:mtd><mml:mn>2</mml:mn>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:mrow>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
pairs) and use the results to annotate the sequences with their conserved areas. To perform the alignment, one can use methods such as the Smith-Waterman local alignment [<xref rid="pone.0161338.ref016" ref-type="bibr">16</xref>
] or related heuristics such as PSI-BLAST [<xref rid="pone.0161338.ref010" ref-type="bibr">10</xref>
, <xref rid="pone.0161338.ref015" ref-type="bibr">15</xref>
]. However, these approaches are not scalable when |<italic>S</italic>
| is large. Instead we generate a new representative vector for each sequence—<italic>k</italic>
-mer profile as defined below—and perform a binary classification using feature vectors obtained from this representation. Rather than dissecting the sequence itself we dissect the profile vector into putative conserved regions and map these conserved regions onto the same indices of the sequence. As we will see in the Results section, the detected putative conserved regions widely correspond to the sequence domain regions of the sequences as they are annotated in well-known protein domain databases.</p>
<p><bold>Definition 3</bold>
<italic>k</italic>
-mer profile: <italic>The k</italic>
-mer profile <italic>of a sequence s is a vector of the length of the sequence, where the value of each index is the frequency of the k-mer originating at that index in s</italic>
.</p>
<p>The problem of parsing a profile vector into putative conserved regions can be translated into a classification problem in which the task is to decide whether or not each index of the vector should be included in a conserved region. We generate an instance for each index of the profile vector and use a trained model to predict whether it belongs to a conserved region; this is a binary classification problem. Because the trained model depends only on the frequency values of each index in its profile vector rather than on the amino acid elements themselves, once we have a well-trained model it can be used for de novo detection of conserved regions. The details for each of these steps is explained below.</p>
<sec id="sec007"><title>Sequence <italic>k</italic>
-mer Profile Generation</title>
<p>A <italic>k</italic>
-mer profile is an alternative representation of a protein sequence. To construct a <italic>k</italic>
-mer profile we need to count the number of times every <italic>k</italic>
-mer appears in different sequences in our data set and record the counts at the same index at which the <italic>k</italic>
-mer originates in the profile vector. We approach the problem using a two-pass hashing procedure. First, the algorithm reads every protein sequence and for each position index of the sequence computes the <italic>k</italic>
-mer starting at that index. The computed <italic>k</italic>
-mer is then used as a hash key to store the position index number and sequence ID for that <italic>k</italic>
-mer in the hash table. If a <italic>k</italic>
-mer appears multiple times in a sequence, we store all appearances as one entry in the hash table. Thus, the frequency of each <italic>k</italic>
-mer in the data set will equal the number of entries stored for that <italic>k</italic>
-mer in the hash table. When reading of the sequences has been completed, we enter the second pass of the algorithm. The algorithm uses the sequence IDs stored as hash values in the first hash table as the keys to construct a second hash table. The value of each sequence ID (hash key) in the second hash table is the originating index of each <italic>k</italic>
-mer in that sequence along with the frequency of that <italic>k</italic>
-mer. By ordering these frequencies in the hash table based on the index numbers, we essentially generate the <italic>k</italic>
-mer profile for each sequence. The serial computation time for this step is <italic>O</italic>
(<italic>N</italic>
), where <italic>N</italic>
is the total length of the <italic>n</italic>
sequences in the data set. Because the operation on one sequence is independent of another, the algorithm is easily parallelizable. Later in this section we present a MapReduce [<xref rid="pone.0161338.ref017" ref-type="bibr">17</xref>
] implementation.</p>
</sec>
<sec id="sec008"><title>Classification Instance Generation</title>
<p>At the conclusion of the first step we have a set of <italic>k</italic>
-mer profiles that are vectors with index values equal to the number of sequences in the data set that contain the <italic>k</italic>
-mer initiating on the same index in the sequences. The next step is to generate classificaton instances for each index in each sequence of the <italic>k</italic>
-mer profiles. Conversion of <italic>k</italic>
-mer profiles to classification instances allows us to first train a binary classificaton model using known domain data and then to use the model to predict new domains. Given the <italic>k</italic>
-mer profile <italic>p</italic>
for sequence <italic>s</italic>
, we generate one classification instance per index <italic>i</italic>
in <italic>s</italic>
. For such a profile and index, our classification instance is a vector <italic>v</italic>
consisting of 2<italic>w</italic>
+ 1 elements (features) where the 2<italic>w</italic>
+ 1 elements are derived directly from the profile vector by copying the values from the window centered on index <italic>i</italic>
of <italic>p</italic>
and extending from both sides for <italic>w</italic>
indices. These features represent the frequency of <italic>k</italic>
-mers initiating at indices [<italic>i</italic>
− <italic>w</italic>
, <italic>i</italic>
+ <italic>w</italic>
] of the corresponding protein sequence.</p>
</sec>
<sec id="sec009"><title>Classification Model Construction</title>
<p>We train the classification model using classification instances that include a class label indicating whether or not the index associated with the instance is conserved. This is determined by querying domain databases. We also use these instances to test our model. Given the integer-valued features of our problem, the need to handle large data sets, and the non-linearity of the problem (due to the variable level of conservation among different domains), decision trees [<xref rid="pone.0161338.ref018" ref-type="bibr">18</xref>
, <xref rid="pone.0161338.ref019" ref-type="bibr">19</xref>
] seem to be a natural choice to use for training the model. They support automatic feature selection and can learn different thresholds for different features. However, for small <italic>w</italic>
the decision tree will not be able to see the overall picture of the <italic>k</italic>
-mer profile and the model will lose robustness. The tree will be inclined to classify any short-lived increase in frequency as a domain index or a small local fall in frequency as a demonstration of absence of a conserved region. On the other hand, a larger <italic>w</italic>
can result in overfitting the training data. To overcome the disadvantages of a simple decision tree classifier, we use a Random Subspace ensemble method [<xref rid="pone.0161338.ref020" ref-type="bibr">20</xref>
] for which the base estimators are decision trees. This ensemble method constructs multiple decision trees on random subsets of features and classifies an instance based on the majority vote of the decision trees.</p>
<p>Because we are using <italic>k</italic>
-mer profiles in our training set rather than actual protein amino acid sequences, our model depends only on frequencies (the values in the <italic>k</italic>
-mer profiles) rather than on the amino acids. As a consequence, it can detect new conserved regions that were not present in our training set, given that there are enough sequences in the data set containing the conserved region to ensure the high frequency of <italic>k</italic>
-mers in that region. In other words our algorithm is able to detect conserved regions that are present in multiple sequences in our data set, even if they were not annotated previously.</p>
<p>On the other hand, because the model is trained only once and we require accurate performance from that model when presented with new data, the selection of a good training set is crucial to the algorithm. First, the presence of conserved regions in too few sequences in the training set will result in small values in the <italic>k</italic>
-mer profile and can be misleading to the training algorithm. Second, as we increase the size of the training set, we will be adding robustness to the trained classifier because conserved regions with varying frequency profiles will be represented in the training set. Using a large data set acquired from any of the big databases of protein conserved regions as our training set will satisfy both our conditions for the training set and will enable our algorithm to detect new conserved regions.</p>
</sec>
<sec id="sec010"><title>MapReduce Algorithm for Profile Generation</title>
<p>We implement our algorithm in the MapReduce framework [<xref rid="pone.0161338.ref017" ref-type="bibr">17</xref>
]. A MapReduce program consists of two main functions of <italic>map</italic>
and <italic>reduce</italic>
. In the map phase a set of mapper tasks generate KeyValues based on the input. These KeyValue objects are hashed based on their key and redistributed based on the result of the hash. The intermediate hash-based grouping phase is called the <italic>shuffle</italic>
phase. Each reducer task then processes the set of values that are hashed to the same key. A reducer, in turn, can also generate KeyValue objects. The MapReduce paradigm suits data-parallel applications naturally. For our purpose, we exploit the shuffle phase to implement many of our hash-based functionalities in parallel.</p>
<p>In our MapReduce algorithm, initially each mapper reads the input set of sequences. It then generates KeyValue pairs using the <italic>k</italic>
-mers of the sequences as keys and sequence ids and <italic>k</italic>
-mer positions as values. The shuffle step subsequently sorts and redistributes these KeyValues such that each reducer receives one KeyMultiValue object, where all the values corresponding to the same key are sent to a single reducer. Based on the number of different sequence ids present in its MultiValue, each reducer determines the frequency of the <italic>k</italic>
-mer mapped to it and emits a KeyValue, where the key is the sequence id and the value is the frequency of the <italic>k</italic>
-mer and the position of the <italic>k</italic>
-mer in that sequence. After this first complete stage of MapReduce, each reducer will contain frequencies of <italic>k</italic>
-mers for each position in one protein sequence and can construct the <italic>k</italic>
-mer profile for that sequence. The algorithm for this step is shown in Algorithm 1.</p>
<p specific-use="line"><bold>Algorithm 1</bold>
Construction of <italic>k</italic>
-mer profile (<italic>S</italic>
:{<italic>s</italic>
<sub>1</sub>
, <italic>s</italic>
<sub>2</sub>
, …, <italic>s</italic>
<sub><italic>n</italic>
</sub>
}, <italic>k</italic>
)</p>
<p specific-use="line"><bold>for</bold>
each sequence <italic>s</italic>
<sub><italic>i</italic>
</sub>
∈ <italic>S</italic>
with id <inline-formula id="pone.0161338.e002"><alternatives><graphic xlink:href="pone.0161338.e002.jpg" id="pone.0161338.e002g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M2"><mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>i</mml:mi>
</mml:msubsup>
</mml:math>
</alternatives>
</inline-formula>
<bold>do</bold>
</p>
<p specific-use="line"> <bold>for</bold>
each index <italic>j</italic>
in <italic>s</italic>
<sub><italic>i</italic>
</sub>
<bold>do</bold>
</p>
<p specific-use="line"> <italic>s</italic>
′ = <italic>s</italic>
<sub><italic>i</italic>
</sub>
(<italic>j</italic>
, <italic>k</italic>
)</p>
<p specific-use="line"> emit KeyValue <inline-formula id="pone.0161338.e003"><alternatives><graphic xlink:href="pone.0161338.e003.jpg" id="pone.0161338.e003g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M3"><mml:mrow><mml:mi>K</mml:mi>
<mml:mi>V</mml:mi>
<mml:mo>=</mml:mo>
<mml:mo><</mml:mo>
<mml:msup><mml:mi>s</mml:mi>
<mml:mo>′</mml:mo>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>,</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>i</mml:mi>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>></mml:mo>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
</p>
<p specific-use="line"> <bold>end for</bold>
</p>
<p specific-use="line"><bold>end for</bold>
</p>
<p specific-use="line">shuffle all KV’s</p>
<p specific-use="line"><bold>for</bold>
each KeyMultiValue <inline-formula id="pone.0161338.e004"><alternatives><graphic xlink:href="pone.0161338.e004.jpg" id="pone.0161338.e004g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M4"><mml:mrow><mml:mi>K</mml:mi>
<mml:mi>M</mml:mi>
<mml:mi>V</mml:mi>
<mml:mo>=</mml:mo>
<mml:mo><</mml:mo>
<mml:msup><mml:mi>s</mml:mi>
<mml:mo>′</mml:mo>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>,</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>i</mml:mi>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mi>m</mml:mi>
<mml:mo>,</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>k</mml:mi>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>,</mml:mo>
<mml:mo>…</mml:mo>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mi>k</mml:mi>
<mml:mo>,</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>l</mml:mi>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>></mml:mo>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
<bold>do</bold>
</p>
<p specific-use="line"> <italic>count</italic>
= <italic>number</italic>
<italic>of</italic>
<italic>different</italic>
<italic>s</italic>
<sub><italic>id</italic>
</sub>
<italic>in</italic>
<italic>the</italic>
<italic>KMV</italic>
</p>
<p specific-use="line"> <bold>for</bold>
each value <inline-formula id="pone.0161338.e005"><alternatives><graphic xlink:href="pone.0161338.e005.jpg" id="pone.0161338.e005g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M5"><mml:mrow><mml:mi>V</mml:mi>
<mml:mo>=</mml:mo>
<mml:mo>(</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>,</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>p</mml:mi>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
in <italic>KMV</italic>
<bold>do</bold>
</p>
<p specific-use="line"> emit KeyValue <inline-formula id="pone.0161338.e006"><alternatives><graphic xlink:href="pone.0161338.e006.jpg" id="pone.0161338.e006g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M6"><mml:mrow><mml:mo><</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>p</mml:mi>
</mml:msubsup>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>c</mml:mi>
<mml:mi>o</mml:mi>
<mml:mi>u</mml:mi>
<mml:mi>n</mml:mi>
<mml:mi>t</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>></mml:mo>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
</p>
<p specific-use="line"> <bold>end for</bold>
</p>
<p specific-use="line"><bold>end for</bold>
</p>
<p specific-use="line">shuffle all KV’s</p>
<p specific-use="line"><bold>for</bold>
each <inline-formula id="pone.0161338.e007"><alternatives><graphic xlink:href="pone.0161338.e007.jpg" id="pone.0161338.e007g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M7"><mml:mrow><mml:mi>K</mml:mi>
<mml:mi>M</mml:mi>
<mml:mi>V</mml:mi>
<mml:mo>=</mml:mo>
<mml:mo><</mml:mo>
<mml:msubsup><mml:mi>s</mml:mi>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mi>d</mml:mi>
</mml:mrow>
<mml:mi>i</mml:mi>
</mml:msubsup>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:msub><mml:mi>j</mml:mi>
<mml:mn>1</mml:mn>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:mi>c</mml:mi>
<mml:mi>o</mml:mi>
<mml:mi>u</mml:mi>
<mml:mi>n</mml:mi>
<mml:msub><mml:mi>t</mml:mi>
<mml:mrow><mml:mi>j</mml:mi>
<mml:mn>1</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>,</mml:mo>
<mml:mrow><mml:mo>(</mml:mo>
<mml:msub><mml:mi>j</mml:mi>
<mml:mn>2</mml:mn>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:mi>c</mml:mi>
<mml:mi>o</mml:mi>
<mml:mi>u</mml:mi>
<mml:mi>n</mml:mi>
<mml:msub><mml:mi>t</mml:mi>
<mml:mrow><mml:mi>j</mml:mi>
<mml:mn>2</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>,</mml:mo>
<mml:mo>…</mml:mo>
<mml:mo>></mml:mo>
</mml:mrow>
</mml:math>
</alternatives>
</inline-formula>
<bold>do</bold>
</p>
<p specific-use="line"> sort values based on <italic>j</italic>
’s</p>
<p specific-use="line"> return the <italic>count</italic>
s based on sorted <italic>j</italic>
’s</p>
<p specific-use="line"><bold>end for</bold>
</p>
</sec>
<sec id="sec011"><title>Implementation and Software Availability</title>
<p>We have implemented our method, NADDA, in C++ and Python. The C++ code uses the <italic>MRMPI</italic>
library [<xref rid="pone.0161338.ref021" ref-type="bibr">21</xref>
] for MapReduce and the <italic>BOOST</italic>
library. The Python code uses the <italic>scikit-learn</italic>
(v. 0.17) machine learning library [<xref rid="pone.0161338.ref022" ref-type="bibr">22</xref>
]. Software is available as open source at <ext-link ext-link-type="uri" xlink:href="https://bitbucket.org/armenabnousi/nadda">https://bitbucket.org/armenabnousi/nadda</ext-link>
.</p>
</sec>
</sec>
<sec sec-type="results" id="sec012"><title>Results</title>
<sec id="sec013"><title>Experimental Setup</title>
<p>Eleven different data sets were used for our experiments, one consisting of approximately 50,000 bacterial protein sequences and the remainder consisting of smaller sets of a few thousand protein sequences each. Some of the latter sets consist entirely of bacterial protein sequences; others are mixtures of sequences from bacteria, eukaryota, and archaea. The number of sequences and percentage of bacterial sequences in each of the smaller sets are listed in <xref rid="pone.0161338.t001" ref-type="table">Table 1</xref>
. More information regarding the domains in each of these is shown in Tables <xref rid="pone.0161338.t002" ref-type="table">2</xref>
to <xref rid="pone.0161338.t011" ref-type="table">11</xref>
. The smaller sets (#1-#10) were used to evaluate <italic>de novo</italic>
detection of conserved regions with our model and to compare it with MKDOM2 [<xref rid="pone.0161338.ref005" ref-type="bibr">5</xref>
], ADDA [<xref rid="pone.0161338.ref003" ref-type="bibr">3</xref>
], and InterPro [<xref rid="pone.0161338.ref023" ref-type="bibr">23</xref>
]. The large data set #11 (<xref rid="pone.0161338.t012" ref-type="table">Table 12</xref>
) was used to train and test our classification model. Because both MKDOM2 and ADDA require sequence alignment, an expensive operation, it was infeasible for us to conduct a comparison using our largest data set. For example, MKDOM2 had not completed its run on data set #11 after 20 days. It should also be noted that both methods focus on clustering proteins based on domain families rather than on detection of conserved regions. MKDOM2 clusters are generated based on regions in sequences with high sequence similarity. These regions represent conserved regions as defined earlier. Similarly, as an initial step ADDA selects some putative domain regions. An optimization objective is then used to generate final domain boundaries on each sequence. These boundaries are later used to construct a graph and perform clustering. While each identified region (indices enclosed between two consecutive boundaries) is expected to contain exactly one domain, because they are used as an intermediate result ADDA does not guarantee that a complete domain will be captured in each domain region predicted by the optimization procedure (i.e., it does not guarantee that there will not be any non-domain indices inside the predicted region). However, a comparison can still be made.</p>
<table-wrap id="pone.0161338.t001" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t001</object-id>
<label>Table 1</label>
<caption><title>Structure of small data sets (#1-#10) used for evaluation of de novo detection of conserved regions and for runtime studies.</title>
</caption>
<alternatives><graphic id="pone.0161338.t001g" xlink:href="pone.0161338.t001"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Data Set</th>
<th align="right" rowspan="1" colspan="1">#sequences</th>
<th align="right" rowspan="1" colspan="1">% bacteria</th>
<th align="right" rowspan="1" colspan="1">% archaea</th>
<th align="right" rowspan="1" colspan="1">% eukaryota</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">#1</td>
<td align="right" rowspan="1" colspan="1">1,424</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#2</td>
<td align="right" rowspan="1" colspan="1">1,542</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#3</td>
<td align="right" rowspan="1" colspan="1">1,479</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#4</td>
<td align="right" rowspan="1" colspan="1">1,494</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
<td align="right" rowspan="1" colspan="1">0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#5</td>
<td align="right" rowspan="1" colspan="1">2,037</td>
<td align="right" rowspan="1" colspan="1">95.4%</td>
<td align="right" rowspan="1" colspan="1">2.6%</td>
<td align="right" rowspan="1" colspan="1">2.0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#6</td>
<td align="right" rowspan="1" colspan="1">808</td>
<td align="right" rowspan="1" colspan="1">93.1%</td>
<td align="right" rowspan="1" colspan="1">3.4%</td>
<td align="right" rowspan="1" colspan="1">3.5%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#7</td>
<td align="right" rowspan="1" colspan="1">2,565</td>
<td align="right" rowspan="1" colspan="1">63.4%</td>
<td align="right" rowspan="1" colspan="1">1.2%</td>
<td align="right" rowspan="1" colspan="1">35.4%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#8</td>
<td align="right" rowspan="1" colspan="1">2,031</td>
<td align="right" rowspan="1" colspan="1">48.9%</td>
<td align="right" rowspan="1" colspan="1">0</td>
<td align="right" rowspan="1" colspan="1">51.1%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#9</td>
<td align="right" rowspan="1" colspan="1">2,138</td>
<td align="right" rowspan="1" colspan="1">29.5%</td>
<td align="right" rowspan="1" colspan="1">1.7%</td>
<td align="right" rowspan="1" colspan="1">68.8%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#10</td>
<td align="right" rowspan="1" colspan="1">1,938</td>
<td align="right" rowspan="1" colspan="1">11.4%</td>
<td align="right" rowspan="1" colspan="1">1.8%</td>
<td align="right" rowspan="1" colspan="1">86.8%</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t002" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t002</object-id>
<label>Table 2</label>
<caption><title>Data Set #1.</title>
</caption>
<alternatives><graphic id="pone.0161338.t002g" xlink:href="pone.0161338.t002"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">FAD_binding_9</td>
<td align="center" rowspan="1" colspan="1">750</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">FixS</td>
<td align="center" rowspan="1" colspan="1">350</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Gas_vesicle</td>
<td align="center" rowspan="1" colspan="1">368</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">1,424</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t003" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t003</object-id>
<label>Table 3</label>
<caption><title>Data Set #2.</title>
</caption>
<alternatives><graphic id="pone.0161338.t003g" xlink:href="pone.0161338.t003"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">Caa3_CtaG</td>
<td align="center" rowspan="1" colspan="1">499</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Dak1_2</td>
<td align="center" rowspan="1" colspan="1">699</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">dCache_3</td>
<td align="center" rowspan="1" colspan="1">351</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">1,542</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t004" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t004</object-id>
<label>Table 4</label>
<caption><title>Data Set #3.</title>
</caption>
<alternatives><graphic id="pone.0161338.t004g" xlink:href="pone.0161338.t004"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">XisI</td>
<td align="center" rowspan="1" colspan="1">213</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">NapB</td>
<td align="center" rowspan="1" colspan="1">179</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">EutN_CcmL</td>
<td align="center" rowspan="1" colspan="1">330</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">LptC</td>
<td align="center" rowspan="1" colspan="1">823</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">1,479</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t005" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t005</object-id>
<label>Table 5</label>
<caption><title>Data Set #4.</title>
</caption>
<alternatives><graphic id="pone.0161338.t005g" xlink:href="pone.0161338.t005"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">EpsG</td>
<td align="center" rowspan="1" colspan="1">313</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">RcnB</td>
<td align="center" rowspan="1" colspan="1">207</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">FlgN</td>
<td align="center" rowspan="1" colspan="1">542</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Lipoprotein_17</td>
<td align="center" rowspan="1" colspan="1">353</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">LolA_like</td>
<td align="center" rowspan="1" colspan="1">344</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">1,494</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t006" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t006</object-id>
<label>Table 6</label>
<caption><title>Data Set #5.</title>
</caption>
<alternatives><graphic id="pone.0161338.t006g" xlink:href="pone.0161338.t006"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">NA37</td>
<td align="center" rowspan="1" colspan="1">384</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">DbpA</td>
<td align="center" rowspan="1" colspan="1">1,232</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">AAA_PrkA</td>
<td align="center" rowspan="1" colspan="1">426</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">2,037</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t007" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t007</object-id>
<label>Table 7</label>
<caption><title>Data Set #6.</title>
</caption>
<alternatives><graphic id="pone.0161338.t007g" xlink:href="pone.0161338.t007"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">NA37</td>
<td align="center" rowspan="1" colspan="1">384</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">AAA_PrkA</td>
<td align="center" rowspan="1" colspan="1">426</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">808</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t008" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t008</object-id>
<label>Table 8</label>
<caption><title>Data Set #7.</title>
</caption>
<alternatives><graphic id="pone.0161338.t008g" xlink:href="pone.0161338.t008"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">Rad4</td>
<td align="center" rowspan="1" colspan="1">693</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">YccF</td>
<td align="center" rowspan="1" colspan="1">1,034</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">DbpA</td>
<td align="center" rowspan="1" colspan="1">1,232</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">2,565</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t009" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t009</object-id>
<label>Table 9</label>
<caption><title>Data Set #8.</title>
</caption>
<alternatives><graphic id="pone.0161338.t009g" xlink:href="pone.0161338.t009"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">RbsD_FucU</td>
<td align="center" rowspan="1" colspan="1">567</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Vasohibin</td>
<td align="center" rowspan="1" colspan="1">180</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">NA37</td>
<td align="center" rowspan="1" colspan="1">384</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Ndc1_Nup</td>
<td align="center" rowspan="1" colspan="1">431</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">2,031</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t010" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t010</object-id>
<label>Table 10</label>
<caption><title>Data Set #9.</title>
</caption>
<alternatives><graphic id="pone.0161338.t010g" xlink:href="pone.0161338.t010"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">AAA_PrkA</td>
<td align="center" rowspan="1" colspan="1">426</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Dnal_N</td>
<td align="center" rowspan="1" colspan="1">140</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">FTCD</td>
<td align="center" rowspan="1" colspan="1">262</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">FACT-Spt16_Nlob</td>
<td align="center" rowspan="1" colspan="1">433</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">SAD_SRA</td>
<td align="center" rowspan="1" colspan="1">890</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">2,138</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t011" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t011</object-id>
<label>Table 11</label>
<caption><title>Data Set #10.</title>
</caption>
<alternatives><graphic id="pone.0161338.t011g" xlink:href="pone.0161338.t011"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Domain Name</th>
<th align="center" rowspan="1" colspan="1">#sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">Has-barrel</td>
<td align="center" rowspan="1" colspan="1">135</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">EccE</td>
<td align="center" rowspan="1" colspan="1">122</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">EFhand_Ca_insen</td>
<td align="center" rowspan="1" colspan="1">724</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">KA1</td>
<td align="center" rowspan="1" colspan="1">959</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">1,938</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<table-wrap id="pone.0161338.t012" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t012</object-id>
<label>Table 12</label>
<caption><title>Common bacterial protein domains used for construction of data set #11.</title>
</caption>
<alternatives><graphic id="pone.0161338.t012g" xlink:href="pone.0161338.t012"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Protein Domain Name</th>
<th align="center" rowspan="1" colspan="1">Number of Sequences</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">TOP1Bc</td>
<td align="center" rowspan="1" colspan="1">11,545</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">CBM_2</td>
<td align="center" rowspan="1" colspan="1">726</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">ZnMc</td>
<td align="center" rowspan="1" colspan="1">2,967</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">ZipA_C</td>
<td align="center" rowspan="1" colspan="1">1,508</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">HLH</td>
<td align="center" rowspan="1" colspan="1">16</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">NADH-G_4Fe-4S_3</td>
<td align="center" rowspan="1" colspan="1">5,476</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">POLAc</td>
<td align="center" rowspan="1" colspan="1">7,110</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">PP2Ac</td>
<td align="center" rowspan="1" colspan="1">907</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Resolvase</td>
<td align="center" rowspan="1" colspan="1">16,007</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">S_TKc</td>
<td align="center" rowspan="1" colspan="1">1,519</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Endonuclease_NS</td>
<td align="center" rowspan="1" colspan="1">2,435</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">total</td>
<td align="center" rowspan="1" colspan="1">50,214</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<p>To obtain our large data set (#11), we queried the SMART [<xref rid="pone.0161338.ref024" ref-type="bibr">24</xref>
] protein domain database (<ext-link ext-link-type="uri" xlink:href="http://smart.embl-heidelberg.de">http://smart.embl-heidelberg.de</ext-link>
) using eleven common bacterial protein domains listed in <xref rid="pone.0161338.t012" ref-type="table">Table 12</xref>
. This resulted in a list of 50,214 bacterial protein sequences that included one or more of the eleven domains. We then queried Pfam-A [<xref rid="pone.0161338.ref025" ref-type="bibr">25</xref>
] release 29.0 with each of these sequences and labeled the domain indices to use as ground-truth for our training instances. For the smaller mixed protein data sets, we randomly selected some protein families through the Pfam webpage (<ext-link ext-link-type="uri" xlink:href="http://pfam.xfam.org">http://pfam.xfam.org</ext-link>
; v.29) and then ran Pfam 29.0 on those sequences to mark their Pfam domain regions. Similarly, for the predominantly bacterial protein data sets, we either randomly identified bacterial protein families through the Pfam webpage or else used domains from the other data sets that had a high bacterial percentage. Again, we marked their domain regions using Pfam 29.0. Tables <xref rid="pone.0161338.t002" ref-type="table">2</xref>
to <xref rid="pone.0161338.t011" ref-type="table">11</xref>
show the protein families selected from the Pfam online database and the number of sequences present in each data set. Totals in these tables are computed after removing common redundant sequences. We then queried InterPro (v5.18-57) using each of our 10 smaller data sets.</p>
<p>Comparisons were performed based on the coverage of the domain indices reported by Pfam-A in our findings and in the MKDOM2 and ADDA results as well as on the coverage of conserved region indices reported by InterPro in the NADDA results. We measured coverage using the three values of accuracy (AC), specificity (SP), and sensitivity (SN) of the detected conserved indices as defined respectively by:
<disp-formula id="pone.0161338.e008"><alternatives><graphic xlink:href="pone.0161338.e008.jpg" id="pone.0161338.e008g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M8"><mml:mrow><mml:mi>A</mml:mi>
<mml:mi>C</mml:mi>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:mrow><mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>P</mml:mi>
<mml:mo>|</mml:mo>
<mml:mo>+</mml:mo>
<mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>N</mml:mi>
<mml:mo>|</mml:mo>
</mml:mrow>
<mml:mi>N</mml:mi>
</mml:mfrac>
</mml:mrow>
</mml:math>
</alternatives>
</disp-formula>
<disp-formula id="pone.0161338.e009"><alternatives><graphic xlink:href="pone.0161338.e009.jpg" id="pone.0161338.e009g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M9"><mml:mrow><mml:mi>S</mml:mi>
<mml:mi>N</mml:mi>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:mrow><mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>P</mml:mi>
<mml:mo>|</mml:mo>
</mml:mrow>
<mml:mrow><mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>P</mml:mi>
<mml:mo>|</mml:mo>
<mml:mo>+</mml:mo>
<mml:mo>|</mml:mo>
<mml:mi>F</mml:mi>
<mml:mi>N</mml:mi>
<mml:mo>|</mml:mo>
</mml:mrow>
</mml:mfrac>
</mml:mrow>
</mml:math>
</alternatives>
</disp-formula>
<disp-formula id="pone.0161338.e010"><alternatives><graphic xlink:href="pone.0161338.e010.jpg" id="pone.0161338.e010g" mimetype="image" position="anchor" orientation="portrait"></graphic>
<mml:math id="M10"><mml:mrow><mml:mi>S</mml:mi>
<mml:mi>P</mml:mi>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:mrow><mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>N</mml:mi>
<mml:mo>|</mml:mo>
</mml:mrow>
<mml:mrow><mml:mo>|</mml:mo>
<mml:mi>T</mml:mi>
<mml:mi>N</mml:mi>
<mml:mo>|</mml:mo>
<mml:mo>+</mml:mo>
<mml:mo>|</mml:mo>
<mml:mi>F</mml:mi>
<mml:mi>P</mml:mi>
<mml:mo>|</mml:mo>
</mml:mrow>
</mml:mfrac>
</mml:mrow>
</mml:math>
</alternatives>
</disp-formula>
where <italic>TP</italic>
, true positives, indicate the indices in the data set that are marked as part of a domain region in Pfam-A, and the detection method also has classified them as conserved indices; <italic>TN</italic>
, true negatives, are the indices that both Pfam-A and the conserved region detection method have not included in any domain/conserved region; <italic>FP</italic>
, false positives, are the indices that are not marked by Pfam-A as contained in a domain, but the detection method has classified them as conserved indices; and <italic>FN</italic>
, false negatives, are the indices that are included in a Pfam-A domain, but the detection method has fallen short of identifying them as conserved. Finally, <italic>N</italic>
is the total length of the sequences in the set (<italic>N</italic>
= |<italic>TP</italic>
| + |<italic>TN</italic>
| + |<italic>FP</italic>
| + |<italic>FN</italic>
|).</p>
<p>For our experiments, unless otherwise stated, values for <italic>w</italic>
(where 2<italic>w</italic>
+ 1 is the size of the feature vector), <italic>k</italic>
(size of each <italic>k</italic>
-mer), <italic>MSS</italic>
(which indicates the level of pruning of the decision tree—minimum number of instances in each internal node), and <italic>max</italic>
_<italic>features</italic>
(number of features used in each decision tree for the ensemble method) are set respectively to 10, 6, 100, and 7. We discuss parameter selection in greater detail in the Supporting Information (<xref ref-type="supplementary-material" rid="pone.0161338.s001">S1 File</xref>
).</p>
</sec>
<sec id="sec014"><title>Evaluation of Results</title>
<p>We evaluate our results in three phases. First, we evaluate our training method by partitioning data set #11 into training and test sets. This is the common practice in the machine learning community for evaluation of a training method. The second phase includes comprehensive experiments evaluating overall performance of NADDA by testing it using data sets with domains that are new to NADDA (data sets #1—#10). Here we also compare NADDA with ADDA and MKDOM2. Finally, in the third phase, we compare NADDA against InterPro, re-evaluating its ability to capture regions that are missed in Pfam. In addition, we provide some example sequences from data sets #1-#10, comparing our detected conserved regions with the segments annotated by InterPro.</p>
<p><bold>Evaluating the training method:</bold>
In the first phase of our experiments we perform two different types of training-set/test-set partitioning of data set #11, training the model on a training set and measuring the results on a test set. First, we divide data set #11 by randomly selecting 20% of the sequences to be included in the test set and the rest in the training set. The second partitioning is performed by selecting 20% of the domains from data set #11 that are present in more than 50 sequences and including every sequence that contains one (or more) of these selected domains in the test set. The reason for setting a threshold for presence of a domain in a sequence in order to be considered a candidate for the test set is explained in the Supporting Information section(<xref ref-type="supplementary-material" rid="pone.0161338.s002">S2 File</xref>
). We refer to the first train/test partition as repetitive and the second one as non-repetitive. The reason for the two different partitions is that while our repetitive partitioning method is widely accepted in the machine learning community, here it can result in overfitting. Because our method depends on the frequency of repeating <italic>k</italic>
-mers, we require that multiple sequences possibly very similar to each other be present in our data set. Dividing the data based on random selection of sequences might result in having similar sequences in the training and test sets. The results achieved might then represent the case when the domain in the query sequence has already been discovered in similar sequences and we are only trying to retrieve this knowledge. In contrast, for our non-repetitive partitioning, because we withhold a set of domains from the training set, the results are better representative of discovering new domains that were not previously known as well as domains that were previously known. This partition is better representative of the results we would obtain using the current knowledge-base of protein conserved regions for new sequences.</p>
<p>The results for the two sets are shown in <xref rid="pone.0161338.t013" ref-type="table">Table 13</xref>
. For the repetitive case the accuracy is 83% with 96% recall (sensitivity). For the non-repetitive case, as expected, the numbers decrease. However, we can still predict with 80% accuracy whether or not a location in a protein sequence is included in a conserved region.</p>
<table-wrap id="pone.0161338.t013" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t013</object-id>
<label>Table 13</label>
<caption><title>Performance of NADDA based on Pfam; When similar domains are present in the training set (repetitive) and when some domains are withheld from the training set (non-repetitive).</title>
</caption>
<alternatives><graphic id="pone.0161338.t013g" xlink:href="pone.0161338.t013"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="center" rowspan="1" colspan="1"></th>
<th align="right" rowspan="1" colspan="1">AC</th>
<th align="right" rowspan="1" colspan="1">SN</th>
<th align="right" rowspan="1" colspan="1">SP</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">Repetitive</td>
<td align="char" char="." rowspan="1" colspan="1">83.4%</td>
<td align="char" char="." rowspan="1" colspan="1">96.9%</td>
<td align="char" char="." rowspan="1" colspan="1">44.1%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Non-repetitive</td>
<td align="char" char="." rowspan="1" colspan="1">80.5%</td>
<td align="char" char="." rowspan="1" colspan="1">95.7%</td>
<td align="char" char="." rowspan="1" colspan="1">25.3%</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<p><bold>Comparison with other methods against Pfam:</bold>
In the second phase of the evaluation we compare our results with final sequence segments produced by MKDOM2 in clustering based on domain families and with final partitions found by the optimization method used in ADDA assuming that Pfam domains represent the ground-truth. As mentioned earlier, MKDOM2 performs clustering by selecting the shortest possible subsequence to be considered as a conserved region and aligning that subsequence with the remaining sequences. The final reported subsequences that have been aligned with each other represent conserved regions on the sequences and can be compared to our detected conserved regions. Similarly, ADDA performs clustering by first selecting a set of putative domain regions and optimizing the boundaries between these provisional domains to construct a protein similarity graph based on detected domains. Although clustering is performed after graph construction and additional filters in these later steps can affect the quality of ADDA clustering, we can use the optimized domain boundaries to compare their pre-computed domains with our method.</p>
<p>We trained our model using data set #11 and tested using data sets #1-#10. Because other methods depend on pairwise sequence similarity and BLAST results, we were forced to pick smaller sets for testing purposes. As mentioned earlier, MKDOM2 ran for 20 days on data set #11 without completion, and ADDA took long even for the small data sets as we will show later in Runtime Study section. We used MKDOM2 from the Xdom2.0 [<xref rid="pone.0161338.ref005" ref-type="bibr">5</xref>
] package and the ADDA implementation obtained from its webpage (using the default settings: <italic>K</italic>
= 73.70676, <italic>C</italic>
= 8.33957, <italic>E</italic>
= 0.05273, <italic>M</italic>
= 1.417, <italic>N</italic>
= 0.008 and <italic>r</italic>
= 1, except for 100 maximum iterations (<italic>i</italic>
= 100); in many of the cases the program stopped after only a few iterations. We also used BLAST+ v2.2.31 to generate the input files for ADDA). <xref ref-type="fig" rid="pone.0161338.g001">Fig 1</xref>
represents our findings. The circle displays our three metrics of accuracy (AC), sensitivity (SN), and specificity (SP) for the three different methods: ADDA (blue), MKDOM2 (green), and NADDA (red). The outermost circle represents 100% of the related measure and the center of the circle represents 0%. For each section (AC, SN, and SP) the bacterial percentage of the protein sequences in the data set for each point decreases in the clockwise direction; the first four points in each section correspond to 100% bacterial data sets. <xref rid="pone.0161338.t014" ref-type="table">Table 14</xref>
shows the detailed results for the same measurements. NADDA shows higher accuracy for all but two of the test sets when compared to MKDOM2 and higher or comparable accuracy for many of the sets when compared to ADDA. MKDOM2 generally has better specificity scores (average 60.7%) than both ADDA and NADDA while its sensitivity scores are worse (average 51.5%). The advantage of specificity over sensitivity in MKDOM2 may be a result of two factors. First, MKDOM2 uses a high-cut off value in PSI-BLAST for the sake of runtime during its heuristic sequence alignment, thereby trading off sensitivity. Second, the greedy nature of the MKDOM2 algorithm inhibits precise detection of domain regions. ADDA shows higher than 99% sensitivity in all cases but very low specificity (4.6% on average). This is because the optimization method in ADDA tries to detect putative domain boundaries rather than domains themselves and the results are later used for graph construction together with some filters in order to achieve final clustering. As a result, ADDA does not care about mislabeling extra positions as long as the boundary between two domains is preserved. These extra indices could possibly be filtered in the graph construction and clustering process.</p>
<fig id="pone.0161338.g001" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.g001</object-id>
<label>Fig 1</label>
<caption><title>Comparison of results from NADDA, ADDA, and MKDOM2 with Pfam on small data sets.</title>
<p>(AC = accuracy, SN = sensitivity, SP = specificity).</p>
</caption>
<graphic xlink:href="pone.0161338.g001"></graphic>
</fig>
<table-wrap id="pone.0161338.t014" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t014</object-id>
<label>Table 14</label>
<caption><title>Performance of the algorithm compared to other methods based on Pfam.</title>
</caption>
<alternatives><graphic id="pone.0161338.t014g" xlink:href="pone.0161338.t014"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="2" colspan="1">Data Set</th>
<th align="right" rowspan="2" colspan="1">Percentage Bacterial</th>
<th align="center" rowspan="2" colspan="1">Mean Freq.</th>
<th align="center" rowspan="2" colspan="1">Freq. Variance</th>
<th align="center" colspan="3" rowspan="1">NADDA</th>
<th align="center" colspan="3" rowspan="1">ADDA</th>
<th align="center" colspan="3" rowspan="1">MKDOM2</th>
</tr>
<tr><th align="right" rowspan="1" colspan="1">AC</th>
<th align="right" rowspan="1" colspan="1">SN</th>
<th align="right" rowspan="1" colspan="1">SP</th>
<th align="right" rowspan="1" colspan="1">AC</th>
<th align="right" rowspan="1" colspan="1">SN</th>
<th align="right" rowspan="1" colspan="1">SP</th>
<th align="right" rowspan="1" colspan="1">AC</th>
<th align="right" rowspan="1" colspan="1">SN</th>
<th align="right" rowspan="1" colspan="1">SP</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">#1</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="char" char="." rowspan="1" colspan="1">5.9</td>
<td align="char" char="." rowspan="1" colspan="1">169.1</td>
<td align="char" char="." rowspan="1" colspan="1">64.9%</td>
<td align="char" char="." rowspan="1" colspan="1">61.9%</td>
<td align="char" char="." rowspan="1" colspan="1">73.0%</td>
<td align="char" char="." rowspan="1" colspan="1">82.7%</td>
<td align="char" char="." rowspan="1" colspan="1">99.5%</td>
<td align="char" char="." rowspan="1" colspan="1">3.7%</td>
<td align="char" char="." rowspan="1" colspan="1">45.4%</td>
<td align="char" char="." rowspan="1" colspan="1">35.5%</td>
<td align="char" char="." rowspan="1" colspan="1">72.0%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#2</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="char" char="." rowspan="1" colspan="1">13.4</td>
<td align="char" char="." rowspan="1" colspan="1">3,386.4</td>
<td align="char" char="." rowspan="1" colspan="1">65.1%</td>
<td align="char" char="." rowspan="1" colspan="1">61.1%</td>
<td align="char" char="." rowspan="1" colspan="1">73.5%</td>
<td align="char" char="." rowspan="1" colspan="1">78.1%</td>
<td align="char" char="." rowspan="1" colspan="1">99.6%</td>
<td align="char" char="." rowspan="1" colspan="1">4.9%</td>
<td align="char" char="." rowspan="1" colspan="1">36.9%</td>
<td align="char" char="." rowspan="1" colspan="1">25.0%</td>
<td align="char" char="." rowspan="1" colspan="1">61.8%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#3</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="char" char="." rowspan="1" colspan="1">2.5</td>
<td align="char" char="." rowspan="1" colspan="1">30.2</td>
<td align="char" char="." rowspan="1" colspan="1">47.8%</td>
<td align="char" char="." rowspan="1" colspan="1">37.2%</td>
<td align="char" char="." rowspan="1" colspan="1">94.5%</td>
<td align="char" char="." rowspan="1" colspan="1">82.7%</td>
<td align="char" char="." rowspan="1" colspan="1">99.4%</td>
<td align="char" char="." rowspan="1" colspan="1">9.3%</td>
<td align="char" char="." rowspan="1" colspan="1">72.7%</td>
<td align="char" char="." rowspan="1" colspan="1">77.5%</td>
<td align="char" char="." rowspan="1" colspan="1">51.4%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#4</td>
<td align="right" rowspan="1" colspan="1">100%</td>
<td align="char" char="." rowspan="1" colspan="1">1.4</td>
<td align="char" char="." rowspan="1" colspan="1">3.3</td>
<td align="char" char="." rowspan="1" colspan="1">42.6%</td>
<td align="char" char="." rowspan="1" colspan="1">12.5%</td>
<td align="char" char="." rowspan="1" colspan="1">86.2%</td>
<td align="char" char="." rowspan="1" colspan="1">69.1%</td>
<td align="char" char="." rowspan="1" colspan="1">99.0%</td>
<td align="char" char="." rowspan="1" colspan="1">3.1%</td>
<td align="char" char="." rowspan="1" colspan="1">50.9%</td>
<td align="char" char="." rowspan="1" colspan="1">54.7%</td>
<td align="char" char="." rowspan="1" colspan="1">42.7%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#5</td>
<td align="right" rowspan="1" colspan="1">95.4%</td>
<td align="char" char="." rowspan="1" colspan="1">36.3</td>
<td align="char" char="." rowspan="1" colspan="1">13,466.3</td>
<td align="char" char="." rowspan="1" colspan="1">76.3%</td>
<td align="char" char="." rowspan="1" colspan="1">85.7%</td>
<td align="char" char="." rowspan="1" colspan="1">48.9%</td>
<td align="char" char="." rowspan="1" colspan="1">74.6%</td>
<td align="char" char="." rowspan="1" colspan="1">99.9%</td>
<td align="char" char="." rowspan="1" colspan="1">2.2%</td>
<td align="char" char="." rowspan="1" colspan="1">55.8%</td>
<td align="char" char="." rowspan="1" colspan="1">56.0%</td>
<td align="char" char="." rowspan="1" colspan="1">54.9%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#6</td>
<td align="right" rowspan="1" colspan="1">93.1%</td>
<td align="char" char="." rowspan="1" colspan="1">23.7</td>
<td align="char" char="." rowspan="1" colspan="1">1,833.9</td>
<td align="char" char="." rowspan="1" colspan="1">78.9%</td>
<td align="char" char="." rowspan="1" colspan="1">79.7%</td>
<td align="char" char="." rowspan="1" colspan="1">67.6%</td>
<td align="char" char="." rowspan="1" colspan="1">93.3%</td>
<td align="char" char="." rowspan="1" colspan="1">99.8%</td>
<td align="char" char="." rowspan="1" colspan="1">6.5%</td>
<td align="char" char="." rowspan="1" colspan="1">25.4%</td>
<td align="char" char="." rowspan="1" colspan="1">23.7%</td>
<td align="char" char="." rowspan="1" colspan="1">47.5%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#7</td>
<td align="right" rowspan="1" colspan="1">63.4%</td>
<td align="char" char="." rowspan="1" colspan="1">25.2</td>
<td align="char" char="." rowspan="1" colspan="1">9,628.8</td>
<td align="char" char="." rowspan="1" colspan="1">64.5%</td>
<td align="char" char="." rowspan="1" colspan="1">86.6%</td>
<td align="char" char="." rowspan="1" colspan="1">42.6%</td>
<td align="char" char="." rowspan="1" colspan="1">51.0%</td>
<td align="char" char="." rowspan="1" colspan="1">99.5%</td>
<td align="char" char="." rowspan="1" colspan="1">3.3%</td>
<td align="char" char="." rowspan="1" colspan="1">62.8%</td>
<td align="char" char="." rowspan="1" colspan="1">60.4%</td>
<td align="char" char="." rowspan="1" colspan="1">65.1%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#8</td>
<td align="right" rowspan="1" colspan="1">48.9%</td>
<td align="char" char="." rowspan="1" colspan="1">10.8</td>
<td align="char" char="." rowspan="1" colspan="1">522.6</td>
<td align="char" char="." rowspan="1" colspan="1">58.6%</td>
<td align="char" char="." rowspan="1" colspan="1">66.1%</td>
<td align="char" char="." rowspan="1" colspan="1">45.1%</td>
<td align="char" char="." rowspan="1" colspan="1">65.9%</td>
<td align="char" char="." rowspan="1" colspan="1">99.4%</td>
<td align="char" char="." rowspan="1" colspan="1">5.5%</td>
<td align="char" char="." rowspan="1" colspan="1">56.6%</td>
<td align="char" char="." rowspan="1" colspan="1">48.9%</td>
<td align="char" char="." rowspan="1" colspan="1">70.7%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#9</td>
<td align="right" rowspan="1" colspan="1">29.5%</td>
<td align="char" char="." rowspan="1" colspan="1">18.2</td>
<td align="char" char="." rowspan="1" colspan="1">1,108.6</td>
<td align="char" char="." rowspan="1" colspan="1">69.1%</td>
<td align="char" char="." rowspan="1" colspan="1">86.3%</td>
<td align="char" char="." rowspan="1" colspan="1">37.4%</td>
<td align="char" char="." rowspan="1" colspan="1">66.1%</td>
<td align="char" char="." rowspan="1" colspan="1">99.5%</td>
<td align="char" char="." rowspan="1" colspan="1">4.2%</td>
<td align="char" char="." rowspan="1" colspan="1">46.5%</td>
<td align="char" char="." rowspan="1" colspan="1">33.7%</td>
<td align="char" char="." rowspan="1" colspan="1">70.3%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">#10</td>
<td align="right" rowspan="1" colspan="1">11.4%</td>
<td align="char" char="." rowspan="1" colspan="1">54.8</td>
<td align="char" char="." rowspan="1" colspan="1">7,183.5</td>
<td align="char" char="." rowspan="1" colspan="1">65.0%</td>
<td align="char" char="." rowspan="1" colspan="1">90.4%</td>
<td align="char" char="." rowspan="1" colspan="1">29.9%</td>
<td align="char" char="." rowspan="1" colspan="1">59.7%</td>
<td align="char" char="." rowspan="1" colspan="1">99.5%</td>
<td align="char" char="." rowspan="1" colspan="1">3.5%</td>
<td align="char" char="." rowspan="1" colspan="1">62.5%</td>
<td align="char" char="." rowspan="1" colspan="1">56.5%</td>
<td align="char" char="." rowspan="1" colspan="1">70.9%</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">Average</td>
<td align="right" rowspan="1" colspan="1">74.17%</td>
<td align="char" char="." rowspan="1" colspan="1">19.22</td>
<td align="char" char="." rowspan="1" colspan="1">3,733.26</td>
<td align="char" char="." rowspan="1" colspan="1">63.3%</td>
<td align="char" char="." rowspan="1" colspan="1">66.7%</td>
<td align="char" char="." rowspan="1" colspan="1">59.9%</td>
<td align="char" char="." rowspan="1" colspan="1">72.3%</td>
<td align="char" char="." rowspan="1" colspan="1">99.5%</td>
<td align="char" char="." rowspan="1" colspan="1">4.6%</td>
<td align="char" char="." rowspan="1" colspan="1">51.5%</td>
<td align="char" char="." rowspan="1" colspan="1">47.1%</td>
<td align="char" char="." rowspan="1" colspan="1">60.7%</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<p>In comparison to the other two methods, we can see that for 4 out of 10 test sets, NADDA exhibits higher than 80% sensitivity. The sensitivity is significantly low for data sets #3 and #4. It is noticeable that for these sets the mean and variance for the <italic>k</italic>
-mer frequency are also smaller than for the other sets. In general there is a correlation between the accuracy of our method and the variance of the <italic>k</italic>
-mer frequency. In fact, the frequency variance depends on our choice of <italic>k</italic>
, and it will increase as <italic>k</italic>
is decreased. However, if <italic>k</italic>
is too small, the variance will be high due to random exact matches that do not signify real conservation. This is discussed further in the Supporting Information section (<xref ref-type="supplementary-material" rid="pone.0161338.s003">S3 File</xref>
).</p>
<p><bold>Comparison against InterPro:</bold>
In the last phase of our evaluation, we compare conserved indices detected by NADDA with regions annotated by InterPro [<xref rid="pone.0161338.ref023" ref-type="bibr">23</xref>
]. InterPro uses predictive models (signatures) generated from multiple databases, including Pfam, SMART, ProDom [<xref rid="pone.0161338.ref013" ref-type="bibr">13</xref>
], prosite [<xref rid="pone.0161338.ref026" ref-type="bibr">26</xref>
], TIGRFAMs [<xref rid="pone.0161338.ref027" ref-type="bibr">27</xref>
], etc. InterPro annotates domains as well as motifs (short conserved regions). As such, there should be more similarity between NADDA and InterPro. We compared our results with InterPro regions. The results are shown in <xref ref-type="fig" rid="pone.0161338.g002">Fig 2</xref>
. Because InterPro includes Pfam, replacing our Pfam annotations with InterPro annotations will only add to the indices marked as conserved in our data sets. This can be manifested by a decrease in our |<italic>FP</italic>
| and |<italic>TN</italic>
|. Indices that we had marked as conserved but Pfam had not might be detected as conserved in InterPro as well, resulting in a smaller |<italic>FP</italic>
|. Similarly indices that neither NADDA nor Pfam detected as conserved might be marked as conserved in InterPro, resulting in a decrease in |<italic>TN</italic>
|. A decrease in |<italic>FP</italic>
| will result in improved <italic>SP</italic>
.</p>
<fig id="pone.0161338.g002" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.g002</object-id>
<label>Fig 2</label>
<caption><title>Comparison of NADDA with InterPro and Pfam using small data sets.</title>
<p>(AC = accuracy, SN = sensitivity, SP = specificity).</p>
</caption>
<graphic xlink:href="pone.0161338.g002"></graphic>
</fig>
<p>It should also be noted that for this comparison we are still using the model trained using Pfam annotations for data set #11. Although this can add to the false examples in the training set, the results show an increase in <italic>SP</italic>
as expected, indicating the robustness of our training method.</p>
<p><xref ref-type="fig" rid="pone.0161338.g003">Fig 3</xref>
shows some example results from our experiments. Training is performed using data set #11, while the sequences shown are from the smaller data sets (#1-#10). The domains present in the smaller data sets are not present in the training set. These examples demonstrate that in many of the indices, the output from NADDA matches with the InterPro annotated regions.</p>
<fig id="pone.0161338.g003" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.g003</object-id>
<label>Fig 3</label>
<caption><title>Comparison between the NADDA outputs and InterPro annotations for a few example sequences.</title>
</caption>
<graphic xlink:href="pone.0161338.g003"></graphic>
</fig>
</sec>
<sec id="sec015"><title>Parametric Study</title>
<p>The parameters used in our method are <italic>k</italic>
, the size of a <italic>k</italic>
-mer; <italic>w</italic>
, where 2<italic>w</italic>
+ 1 is the number of features used in a classification instance; <italic>MSS</italic>
, indicates the level of pruning of the decision tree; and <italic>maximum</italic>
_<italic>features</italic>
, number of features used in the ensemble method. The parameters <italic>w</italic>
, <italic>MSS</italic>
, and <italic>maximum</italic>
_<italic>features</italic>
were set to avoid overfitting and underfitting as explained in the Supporting Information (<xref ref-type="supplementary-material" rid="pone.0161338.s001">S1 File</xref>
). The optimal value for <italic>k</italic>
was found empirically from the set {3, 4, 5, 6, 7, 8}. We have shown the effect of varying <italic>k</italic>
in the Supporting Information (<xref ref-type="supplementary-material" rid="pone.0161338.s003">S3 File</xref>
). Varying <italic>k</italic>
affects the mean frequency of <italic>k</italic>
-mers as well as their variance and, thus, is important in the performance of the method.</p>
</sec>
<sec id="sec016"><title>Runtime Study</title>
<p>We performed a runtime study by comparing the time for a serial run of NADDA with that of ADDA and MKDOM2 and also by a scalability evaluation of NADDA in a parallel environment.</p>
<p>We ran the algorithms on our in-house Linux cluster which includes 8 nodes of 64 AMD processors (2.29GHz), each node having 128GB shared memory. We used ADDA and MKDOM2 implementations as described earlier.</p>
<p><xref rid="pone.0161338.t015" ref-type="table">Table 15</xref>
lists a comparison of runtimes for NADDA, ADDA, and MKDOM2 for data set #7 on a single processor. The runtime for our method does not include the one-time training time. The ADDA runtime presented in <xref rid="pone.0161338.t015" ref-type="table">Table 15</xref>
includes the time required for running BLAST.</p>
<table-wrap id="pone.0161338.t015" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.t015</object-id>
<label>Table 15</label>
<caption><title>Runtimes of different methods for Data Set #7.</title>
<p>The times represented here are for a serial run, i.e., single core. As shown in <xref ref-type="fig" rid="pone.0161338.g004">Fig 4</xref>
, NADDA scales almost linearly in the number of cores, allowing the use of the method on even larger data sets.</p>
</caption>
<alternatives><graphic id="pone.0161338.t015g" xlink:href="pone.0161338.t015"></graphic>
<table frame="box" rules="all" border="0"><colgroup span="1"><col align="left" valign="middle" span="1"></col>
<col align="left" valign="middle" span="1"></col>
</colgroup>
<thead><tr><th align="left" rowspan="1" colspan="1">Method</th>
<th align="right" rowspan="1" colspan="1">Time (s)</th>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">NADDA</td>
<td align="right" rowspan="1" colspan="1">49</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">ADDA</td>
<td align="right" rowspan="1" colspan="1">10,566</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">MKDOM2</td>
<td align="right" rowspan="1" colspan="1">456</td>
</tr>
</tbody>
</table>
</alternatives>
</table-wrap>
<p>We can see that even for a small set of about 2,500 sequences, NADDA finishes much more quickly than the other methods. We ran the parallel implementation of our code on data set #11 (50,000 sequences) and showed that it scales nearly linearly with an increasing number of processors (<xref ref-type="fig" rid="pone.0161338.g004">Fig 4</xref>
). NADDA took 79 seconds using 32 processors to complete this data set given an already trained model. Training was not parallelized and on data set #1 took 61 minutes. Parallel constructions for decision trees are proposed [<xref rid="pone.0161338.ref028" ref-type="bibr">28</xref>
–<xref rid="pone.0161338.ref030" ref-type="bibr">30</xref>
]. A detailed study of our parallel runtime is presented in the Supporting Information section <xref ref-type="supplementary-material" rid="pone.0161338.s004">S4 File</xref>
.</p>
<fig id="pone.0161338.g004" orientation="portrait" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0161338.g004</object-id>
<label>Fig 4</label>
<caption><title>Speedup for parallel execution of NADDA on data set #11.</title>
<p>The dotted line shows the ideal linear speedup; the solid line is the actual speedup using NADDA.</p>
</caption>
<graphic xlink:href="pone.0161338.g004"></graphic>
</fig>
</sec>
</sec>
<sec id="sec017"><title>Conclusions and Future Work</title>
<p>We presented the problem of detection of conserved regions in protein sequences. In the past, multiple methods have been proposed for detection of putative domain regions from protein sequences. However, to the best of our knowledge there is no prior work that focuses on the detection of conserved regions, given a large collection of protein sequences. The method proposed in this paper fills this gap using an alignment-free approach.</p>
<p>We showed that rather than using an amino acid sequence of a protein, we can utilize its vectorized representation for our computation. We presented <italic>k</italic>
-mer profiles of proteins as a new representation for protein sequences which can be useful for increasing the scalability of computation. We presented a MapReduce algorithm for generation of <italic>k</italic>
-mer profiles. We used a random subspace ensemble learning method to improve the accuracy of conserved region detection.</p>
<p>Our experiments show competitive accuracy, sensitivity, and specificity measures for our method when compared to other methods. We also showed that our parallel implementation is scalable and works on large data sets. Our experiments show near-linear speedup.</p>
<p>We showed that our method is able to detect conserved regions of bacterial protein sequences as well as conserved regions of eukaryota and archaea protein sequences. The category of the species does not affect the results of our method. Moreover, we showed that variance of the <italic>k</italic>
-mers from their mean has a correlation with the ability of our method to detect conserved regions. When the variance is low, we may be able to decrease <italic>k</italic>
to obtain higher variance and consequently higher accuracy. Extremely small values of <italic>k</italic>
, however, can result in higher variance due to random exact matches and should be avoided.</p>
<p>Use of structured prediction techniques might increase the accuracy of our algorithm. However, a structured prediction model will likely give higher weights to the context (previous predictions) rather than to other features. Another problem with use of different machine learning algorithms is the large scale of our data.</p>
<p>The iterative MapReduce algorithm fits best in the Spark parallel computing model [<xref rid="pone.0161338.ref031" ref-type="bibr">31</xref>
] which also provides machine learning tools. In future work, we will implement our algorithm using the Spark paradigm.</p>
</sec>
<sec sec-type="supplementary-material" id="sec018"><title>Supporting Information</title>
<supplementary-material content-type="local-data" id="pone.0161338.s001"><label>S1 File</label>
<caption><title>Parameter Selection.</title>
<p>(PDF)</p>
</caption>
<media xlink:href="pone.0161338.s001.pdf"><caption><p>Click here for additional data file.</p>
</caption>
</media>
</supplementary-material>
<supplementary-material content-type="local-data" id="pone.0161338.s002"><label>S2 File</label>
<caption><title>Partitioning the Data Set.</title>
<p>(PDF)</p>
</caption>
<media xlink:href="pone.0161338.s002.pdf"><caption><p>Click here for additional data file.</p>
</caption>
</media>
</supplementary-material>
<supplementary-material content-type="local-data" id="pone.0161338.s003"><label>S3 File</label>
<caption><title>Varying the <italic>k</italic>
-mer Size.</title>
<p>(PDF)</p>
</caption>
<media xlink:href="pone.0161338.s003.pdf"><caption><p>Click here for additional data file.</p>
</caption>
</media>
</supplementary-material>
<supplementary-material content-type="local-data" id="pone.0161338.s004"><label>S4 File</label>
<caption><title>Parallel Performance.</title>
<p>(PDF)</p>
</caption>
<media xlink:href="pone.0161338.s004.pdf"><caption><p>Click here for additional data file.</p>
</caption>
</media>
</supplementary-material>
</sec>
</body>
<back><ack><p>The authors would like to thank Prof. Janardhan (Jana) Rao Doppa (Washington State University) for his advice on the use of machine learning algorithms. This work was funded by support from the U.S. National Science Foundation under the Advances in Biological Informatics program, Award DBI 1262664.</p>
</ack>
<ref-list><title>References</title>
<ref id="pone.0161338.ref001"><label>1</label>
<mixed-citation publication-type="journal"><name><surname>Consortium</surname>
<given-names>U</given-names>
</name>
, <etal>et al</etal>
<article-title>UniProt: a hub for protein information</article-title>
. <source>Nucleic acids research</source>
. <year>2014</year>
; p. gku989.</mixed-citation>
</ref>
<ref id="pone.0161338.ref002"><label>2</label>
<mixed-citation publication-type="journal"><name><surname>Doolittle</surname>
<given-names>RF</given-names>
</name>
, <name><surname>Bork</surname>
<given-names>P</given-names>
</name>
. <article-title>Evolutionarily mobile modules in proteins</article-title>
. <source>Scientific American</source>
. <year>1993</year>
;<volume>269</volume>
(<issue>4</issue>
):<fpage>50</fpage>
<pub-id pub-id-type="doi">10.1038/scientificamerican1093-50</pub-id>
<pub-id pub-id-type="pmid">8235550</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref003"><label>3</label>
<mixed-citation publication-type="journal"><name><surname>Heger</surname>
<given-names>A</given-names>
</name>
, <name><surname>Holm</surname>
<given-names>L</given-names>
</name>
. <article-title>Exhaustive enumeration of protein domain families</article-title>
. <source>Journal of molecular biology</source>
. <year>2003</year>
;<volume>328</volume>
(<issue>3</issue>
):<fpage>749</fpage>
–<lpage>767</lpage>
. <pub-id pub-id-type="doi">10.1016/S0022-2836(03)00269-9</pub-id>
<pub-id pub-id-type="pmid">12706730</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref004"><label>4</label>
<mixed-citation publication-type="journal"><name><surname>Portugaly</surname>
<given-names>E</given-names>
</name>
, <name><surname>Harel</surname>
<given-names>A</given-names>
</name>
, <name><surname>Linial</surname>
<given-names>N</given-names>
</name>
, <name><surname>Linial</surname>
<given-names>M</given-names>
</name>
. <article-title>EVEREST: automatic identification and classification of protein domains in all protein sequences</article-title>
. <source>BMC bioinformatics</source>
. <year>2006</year>
;<volume>7</volume>
(<issue>1</issue>
):<fpage>277</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-7-277</pub-id>
<pub-id pub-id-type="pmid">16749920</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref005"><label>5</label>
<mixed-citation publication-type="journal"><name><surname>Gouzy</surname>
<given-names>J</given-names>
</name>
, <name><surname>Corpet</surname>
<given-names>F</given-names>
</name>
, <name><surname>Kahn</surname>
<given-names>D</given-names>
</name>
. <article-title>Whole genome protein domain analysis using a new method for domain clustering</article-title>
. <source>Computers & chemistry</source>
. <year>1999</year>
;<volume>23</volume>
(<issue>3</issue>
):<fpage>333</fpage>
–<lpage>340</lpage>
. <pub-id pub-id-type="doi">10.1016/S0097-8485(99)00011-X</pub-id>
<pub-id pub-id-type="pmid">10404623</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref006"><label>6</label>
<mixed-citation publication-type="other">Abnousi A, Broschat SL, Kalyanaraman A. An alignment-free approach to cluster proteins using frequency of conserved k-mers. In: Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics. ACM; 2015. p. 597–606.</mixed-citation>
</ref>
<ref id="pone.0161338.ref007"><label>7</label>
<mixed-citation publication-type="journal"><name><surname>Tress</surname>
<given-names>M</given-names>
</name>
, <name><surname>Cheng</surname>
<given-names>J</given-names>
</name>
, <name><surname>Baldi</surname>
<given-names>P</given-names>
</name>
, <name><surname>Joo</surname>
<given-names>K</given-names>
</name>
, <name><surname>Lee</surname>
<given-names>J</given-names>
</name>
, <name><surname>Seo</surname>
<given-names>JH</given-names>
</name>
, <etal>et al</etal>
<article-title>Assessment of predictions submitted for the CASP7 domain prediction category</article-title>
. <source>Proteins: Structure, Function, and Bioinformatics</source>
. <year>2007</year>
;<volume>69</volume>
(<issue>S8</issue>
):<fpage>137</fpage>
–<lpage>151</lpage>
. <pub-id pub-id-type="doi">10.1002/prot.21675</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref008"><label>8</label>
<mixed-citation publication-type="journal"><name><surname>Tai</surname>
<given-names>CH</given-names>
</name>
, <name><surname>Lee</surname>
<given-names>WJ</given-names>
</name>
, <name><surname>Vincent</surname>
<given-names>JJ</given-names>
</name>
, <name><surname>Lee</surname>
<given-names>B</given-names>
</name>
. <article-title>Evaluation of domain prediction in CASP6</article-title>
. <source>PROTEINS: Structure, Function, and Bioinformatics</source>
. <year>2005</year>
;<volume>61</volume>
(<issue>S7</issue>
):<fpage>183</fpage>
–<lpage>192</lpage>
. <pub-id pub-id-type="doi">10.1002/prot.20736</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref009"><label>9</label>
<mixed-citation publication-type="journal"><name><surname>Eickholt</surname>
<given-names>J</given-names>
</name>
, <name><surname>Deng</surname>
<given-names>X</given-names>
</name>
, <name><surname>Cheng</surname>
<given-names>J</given-names>
</name>
. <article-title>DoBo: Protein domain boundary prediction by integrating evolutionary signals and machine learning</article-title>
. <source>BMC bioinformatics</source>
. <year>2011</year>
;<volume>12</volume>
(<issue>1</issue>
):<fpage>43</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-12-43</pub-id>
<pub-id pub-id-type="pmid">21284866</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref010"><label>10</label>
<mixed-citation publication-type="journal"><name><surname>Altschul</surname>
<given-names>SF</given-names>
</name>
, <name><surname>Madden</surname>
<given-names>TL</given-names>
</name>
, <name><surname>Schäffer</surname>
<given-names>AA</given-names>
</name>
, <name><surname>Zhang</surname>
<given-names>J</given-names>
</name>
, <name><surname>Zhang</surname>
<given-names>Z</given-names>
</name>
, <name><surname>Miller</surname>
<given-names>W</given-names>
</name>
, <etal>et al</etal>
<article-title>Gapped BLAST and PSI-BLAST: a new generation of protein database search programs</article-title>
. <source>Nucleic Acids Research</source>
. <year>1997</year>
;<volume>25</volume>
(<issue>17</issue>
):<fpage>3389</fpage>
–<lpage>3402</lpage>
. <pub-id pub-id-type="doi">10.1093/nar/25.17.3389</pub-id>
<pub-id pub-id-type="pmid">9254694</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref011"><label>11</label>
<mixed-citation publication-type="journal"><name><surname>Gouzy</surname>
<given-names>J</given-names>
</name>
, <name><surname>Eugene</surname>
<given-names>P</given-names>
</name>
, <name><surname>Greene</surname>
<given-names>EA</given-names>
</name>
, <name><surname>Kahn</surname>
<given-names>D</given-names>
</name>
, <name><surname>Corpet</surname>
<given-names>F</given-names>
</name>
. <article-title>XDOM, a graphical tool to analyse domain arrangements in any set of protein sequences</article-title>
. <source>Computer applications in the biosciences: CABIOS</source>
. <year>1997</year>
;<volume>13</volume>
(<issue>6</issue>
):<fpage>601</fpage>
–<lpage>608</lpage>
. <pub-id pub-id-type="pmid">9475988</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref012"><label>12</label>
<mixed-citation publication-type="journal"><name><surname>Sonnhammer</surname>
<given-names>EL</given-names>
</name>
, <name><surname>Kahn</surname>
<given-names>D</given-names>
</name>
. <article-title>Modular arrangement of proteins as inferred from analysis of homology</article-title>
. <source>Protein Science</source>
. <year>1994</year>
;<volume>3</volume>
(<issue>3</issue>
):<fpage>482</fpage>
–<lpage>492</lpage>
. <pub-id pub-id-type="doi">10.1002/pro.5560030314</pub-id>
<pub-id pub-id-type="pmid">8019419</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref013"><label>13</label>
<mixed-citation publication-type="journal"><name><surname>Bru</surname>
<given-names>C</given-names>
</name>
, <name><surname>Courcelle</surname>
<given-names>E</given-names>
</name>
, <name><surname>Carrère</surname>
<given-names>S</given-names>
</name>
, <name><surname>Beausse</surname>
<given-names>Y</given-names>
</name>
, <name><surname>Dalmar</surname>
<given-names>S</given-names>
</name>
, <name><surname>Kahn</surname>
<given-names>D</given-names>
</name>
. <article-title>The ProDom database of protein domain families: more emphasis on 3D</article-title>
. <source>Nucleic acids research</source>
. <year>2005</year>
;<volume>33</volume>
(<issue>suppl 1</issue>
):<fpage>D212</fpage>
–<lpage>D215</lpage>
. <pub-id pub-id-type="doi">10.1093/nar/gki034</pub-id>
<pub-id pub-id-type="pmid">15608179</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref014"><label>14</label>
<mixed-citation publication-type="other">Kahn D, Rezvoy C, Vivien F. Parallel large scale inference of protein domain families. In: Parallel and Distributed Systems, 2008. ICPADS’08. 14th IEEE International Conference on. IEEE; 2008. p. 72–79.</mixed-citation>
</ref>
<ref id="pone.0161338.ref015"><label>15</label>
<mixed-citation publication-type="journal"><name><surname>Altschul</surname>
<given-names>SF</given-names>
</name>
, <name><surname>Gish</surname>
<given-names>W</given-names>
</name>
, <name><surname>Miller</surname>
<given-names>W</given-names>
</name>
, <name><surname>Myers</surname>
<given-names>EW</given-names>
</name>
, <name><surname>Lipman</surname>
<given-names>DJ</given-names>
</name>
. <article-title>Basic local alignment search tool</article-title>
. <source>Journal of molecular biology</source>
. <year>1990</year>
;<volume>215</volume>
(<issue>3</issue>
):<fpage>403</fpage>
–<lpage>410</lpage>
. <pub-id pub-id-type="doi">10.1016/S0022-2836(05)80360-2</pub-id>
<pub-id pub-id-type="pmid">2231712</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref016"><label>16</label>
<mixed-citation publication-type="journal"><name><surname>Smith</surname>
<given-names>TF</given-names>
</name>
, <name><surname>Waterman</surname>
<given-names>MS</given-names>
</name>
. <article-title>Identification of common molecular subsequences</article-title>
. <source>Journal of molecular biology</source>
. <year>1981</year>
;<volume>147</volume>
(<issue>1</issue>
):<fpage>195</fpage>
–<lpage>197</lpage>
. <pub-id pub-id-type="doi">10.1016/0022-2836(81)90087-5</pub-id>
<pub-id pub-id-type="pmid">7265238</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref017"><label>17</label>
<mixed-citation publication-type="journal"><name><surname>Dean</surname>
<given-names>J</given-names>
</name>
, <name><surname>Ghemawat</surname>
<given-names>S</given-names>
</name>
. <article-title>MapReduce: simplified data processing on large clusters</article-title>
. <source>Communications of the ACM</source>
. <year>2008</year>
;<volume>51</volume>
(<issue>1</issue>
):<fpage>107</fpage>
–<lpage>113</lpage>
. <pub-id pub-id-type="doi">10.1145/1327452.1327492</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref018"><label>18</label>
<mixed-citation publication-type="book"><name><surname>Breiman</surname>
<given-names>L</given-names>
</name>
, <name><surname>Friedman</surname>
<given-names>JH</given-names>
</name>
, <name><surname>Olshen</surname>
<given-names>RA</given-names>
</name>
, <name><surname>Stone</surname>
<given-names>CJ</given-names>
</name>
. <source>Classification and regression trees Belmont</source>
. <publisher-loc>CA</publisher-loc>
: <publisher-name>Wadsworth International Group</publisher-name>
<year>1984</year>
;.</mixed-citation>
</ref>
<ref id="pone.0161338.ref019"><label>19</label>
<mixed-citation publication-type="journal"><name><surname>Quilan</surname>
<given-names>J</given-names>
</name>
. <article-title>Learning efficient classification procedures and their application to chess end games</article-title>
. <source>Machine Learning: An Artificial Intelligence Approach</source>
. <year>1983</year>
;<volume>1</volume>
<pub-id pub-id-type="doi">10.1007/978-3-662-12405-5_15</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref020"><label>20</label>
<mixed-citation publication-type="journal"><name><surname>Ho</surname>
<given-names>TK</given-names>
</name>
. <article-title>The random subspace method for constructing decision forests</article-title>
. <source>Pattern Analysis and Machine Intelligence, IEEE Transactions on</source>
. <year>1998</year>
;<volume>20</volume>
(<issue>8</issue>
):<fpage>832</fpage>
–<lpage>844</lpage>
. <pub-id pub-id-type="doi">10.1109/34.709601</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref021"><label>21</label>
<mixed-citation publication-type="journal"><name><surname>Plimpton</surname>
<given-names>SJ</given-names>
</name>
, <name><surname>Devine</surname>
<given-names>KD</given-names>
</name>
. <article-title>MapReduce in MPI for large-scale graph algorithms</article-title>
. <source>Parallel Computing</source>
. <year>2011</year>
;<volume>37</volume>
(<issue>9</issue>
):<fpage>610</fpage>
–<lpage>632</lpage>
. <pub-id pub-id-type="doi">10.1016/j.parco.2011.02.004</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref022"><label>22</label>
<mixed-citation publication-type="journal"><name><surname>Pedregosa</surname>
<given-names>F</given-names>
</name>
, <name><surname>Varoquaux</surname>
<given-names>G</given-names>
</name>
, <name><surname>Gramfort</surname>
<given-names>A</given-names>
</name>
, <name><surname>Michel</surname>
<given-names>V</given-names>
</name>
, <name><surname>Thirion</surname>
<given-names>B</given-names>
</name>
, <name><surname>Grisel</surname>
<given-names>O</given-names>
</name>
, <etal>et al</etal>
<article-title>Scikit-learn: Machine Learning in Python</article-title>
. <source>Journal of Machine Learning Research</source>
. <year>2011</year>
;<volume>12</volume>
:<fpage>2825</fpage>
–<lpage>2830</lpage>
.</mixed-citation>
</ref>
<ref id="pone.0161338.ref023"><label>23</label>
<mixed-citation publication-type="journal"><name><surname>Jones</surname>
<given-names>P</given-names>
</name>
, <name><surname>Binns</surname>
<given-names>D</given-names>
</name>
, <name><surname>Chang</surname>
<given-names>HY</given-names>
</name>
, <name><surname>Fraser</surname>
<given-names>M</given-names>
</name>
, <name><surname>Li</surname>
<given-names>W</given-names>
</name>
, <name><surname>McAnulla</surname>
<given-names>C</given-names>
</name>
, <etal>et al</etal>
<article-title>InterProScan 5: genome-scale protein function classification</article-title>
. <source>Bioinformatics</source>
. <year>2014</year>
;<volume>30</volume>
(<issue>9</issue>
):<fpage>1236</fpage>
–<lpage>1240</lpage>
. <pub-id pub-id-type="doi">10.1093/bioinformatics/btu031</pub-id>
<pub-id pub-id-type="pmid">24451626</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref024"><label>24</label>
<mixed-citation publication-type="journal"><name><surname>Schultz</surname>
<given-names>J</given-names>
</name>
, <name><surname>Milpetz</surname>
<given-names>F</given-names>
</name>
, <name><surname>Bork</surname>
<given-names>P</given-names>
</name>
, <name><surname>Ponting</surname>
<given-names>CP</given-names>
</name>
. <article-title>SMART, a simple modular architecture research tool: identification of signaling domains</article-title>
. <source>Proceedings of the National Academy of Sciences</source>
. <year>1998</year>
;<volume>95</volume>
(<issue>11</issue>
):<fpage>5857</fpage>
–<lpage>5864</lpage>
. <pub-id pub-id-type="doi">10.1073/pnas.95.11.5857</pub-id>
</mixed-citation>
</ref>
<ref id="pone.0161338.ref025"><label>25</label>
<mixed-citation publication-type="journal"><name><surname>Finn</surname>
<given-names>RD</given-names>
</name>
, <name><surname>Coggill</surname>
<given-names>P</given-names>
</name>
, <name><surname>Eberhardt</surname>
<given-names>RY</given-names>
</name>
, <name><surname>Eddy</surname>
<given-names>SR</given-names>
</name>
, <name><surname>Mistry</surname>
<given-names>J</given-names>
</name>
, <name><surname>Mitchell</surname>
<given-names>AL</given-names>
</name>
, <etal>et al</etal>
<article-title>The Pfam protein families database: towards a more sustainable future</article-title>
. <source>Nucleic Acids Research</source>
. <year>2015</year>
; p. gkv1344.</mixed-citation>
</ref>
<ref id="pone.0161338.ref026"><label>26</label>
<mixed-citation publication-type="journal"><name><surname>Sigrist</surname>
<given-names>CJ</given-names>
</name>
, <name><surname>De Castro</surname>
<given-names>E</given-names>
</name>
, <name><surname>Cerutti</surname>
<given-names>L</given-names>
</name>
, <name><surname>Cuche</surname>
<given-names>BA</given-names>
</name>
, <name><surname>Hulo</surname>
<given-names>N</given-names>
</name>
, <name><surname>Bridge</surname>
<given-names>A</given-names>
</name>
, <etal>et al</etal>
<article-title>New and continuing developments at PROSITE</article-title>
. <source>Nucleic acids research</source>
. <year>2012</year>
; p. gks1067.</mixed-citation>
</ref>
<ref id="pone.0161338.ref027"><label>27</label>
<mixed-citation publication-type="journal"><name><surname>Haft</surname>
<given-names>DH</given-names>
</name>
, <name><surname>Selengut</surname>
<given-names>JD</given-names>
</name>
, <name><surname>Richter</surname>
<given-names>RA</given-names>
</name>
, <name><surname>Harkins</surname>
<given-names>D</given-names>
</name>
, <name><surname>Basu</surname>
<given-names>MK</given-names>
</name>
, <name><surname>Beck</surname>
<given-names>E</given-names>
</name>
. <article-title>TIGRFAMs and genome properties in 2013</article-title>
. <source>Nucleic acids research</source>
. <year>2012</year>
; p. gks1234.</mixed-citation>
</ref>
<ref id="pone.0161338.ref028"><label>28</label>
<mixed-citation publication-type="book"><name><surname>Srivastava</surname>
<given-names>A</given-names>
</name>
, <name><surname>Han</surname>
<given-names>EH</given-names>
</name>
, <name><surname>Kumar</surname>
<given-names>V</given-names>
</name>
, <name><surname>Singh</surname>
<given-names>V</given-names>
</name>
. <source>Parallel formulations of decision-tree classification algorithms</source>
. <publisher-name>Springer</publisher-name>
; <year>1999</year>
.</mixed-citation>
</ref>
<ref id="pone.0161338.ref029"><label>29</label>
<mixed-citation publication-type="other">Jin R, Agrawal G. Communication and Memory Efficient Parallel Decision Tree Construction. In: SDM. SIAM; 2003. p. 119–129.</mixed-citation>
</ref>
<ref id="pone.0161338.ref030"><label>30</label>
<mixed-citation publication-type="other">Agrawal R, Mehta M, Shafer JC. Method and system for generating a decision-tree classifier in parallel in a multi-processor system; <year>1999</year>
.</mixed-citation>
</ref>
<ref id="pone.0161338.ref031"><label>31</label>
<mixed-citation publication-type="other">Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I. Spark: Cluster Computing with Working Sets. In: Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing. HotCloud’10. Berkeley, CA, USA: USENIX Association; 2010. p. 10–10. Available from: <ext-link ext-link-type="uri" xlink:href="http://dl.acm.org/citation.cfm?id=1863103.1863113">http://dl.acm.org/citation.cfm?id=1863103.1863113</ext-link>
.</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 001025 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 001025 | 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é= PMC:4995020 |texte= A Fast Alignment-Free Approach for De Novo Detection of Protein Conserved Regions }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:27552220" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |