Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time</title>
<author><name sortKey="Kang, Seunghwa" sort="Kang, Seunghwa" uniqKey="Kang S" first="Seunghwa" last="Kang">Seunghwa Kang</name>
<affiliation><nlm:aff id="aff1"><addr-line>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Tang, Jijun" sort="Tang, Jijun" uniqKey="Tang J" first="Jijun" last="Tang">Jijun Tang</name>
<affiliation><nlm:aff id="aff2"><addr-line>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Schaeffer, Stephen W" sort="Schaeffer, Stephen W" uniqKey="Schaeffer S" first="Stephen W." last="Schaeffer">Stephen W. Schaeffer</name>
<affiliation><nlm:aff id="aff3"><addr-line>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Bader, David A" sort="Bader, David A" uniqKey="Bader D" first="David A." last="Bader">David A. Bader</name>
<affiliation><nlm:aff id="aff4"><addr-line>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">21887219</idno>
<idno type="pmc">3160844</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3160844</idno>
<idno type="RBID">PMC:3160844</idno>
<idno type="doi">10.1371/journal.pone.0022483</idno>
<date when="2011">2011</date>
<idno type="wicri:Area/Pmc/Corpus">000643</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time</title>
<author><name sortKey="Kang, Seunghwa" sort="Kang, Seunghwa" uniqKey="Kang S" first="Seunghwa" last="Kang">Seunghwa Kang</name>
<affiliation><nlm:aff id="aff1"><addr-line>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Tang, Jijun" sort="Tang, Jijun" uniqKey="Tang J" first="Jijun" last="Tang">Jijun Tang</name>
<affiliation><nlm:aff id="aff2"><addr-line>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Schaeffer, Stephen W" sort="Schaeffer, Stephen W" uniqKey="Schaeffer S" first="Stephen W." last="Schaeffer">Stephen W. Schaeffer</name>
<affiliation><nlm:aff id="aff3"><addr-line>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania, United States of America</addr-line>
</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Bader, David A" sort="Bader, David A" uniqKey="Bader D" first="David A." last="Bader">David A. Bader</name>
<affiliation><nlm:aff id="aff4"><addr-line>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, 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="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><p>Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious evolutionary scenario using the species' genome data. MP methods are considered to be accurate, but they are also computationally expensive especially for a large number of species. Several disk-covering methods (DCMs), which decompose the input species to multiple overlapping subgroups (or disks), have been proposed to solve the problem in a divide-and-conquer way.</p>
<p>We design a new DCM based on the spectral method and also develop the <italic>COGNAC</italic>
(Comparing Orders of Genes using Novel Algorithms and high-performance Computers) software package. <italic>COGNAC</italic>
uses the new DCM to reduce the phylogenetic tree search space and selects an output tree from the reduced search space based on the MP principle. We test the new DCM using gene order data and inversion distance. The new DCM not only reduces the number of candidate tree topologies but also excludes erroneous tree topologies which can be selected by original MP methods. Initial labeling of internal genomes affects the accuracy of MP methods using gene order data, and the new DCM enables more accurate initial labeling as well. <italic>COGNAC</italic>
demonstrates superior accuracy as a consequence. We compare <italic>COGNAC</italic>
with FastME and the combination of the state of the art DCM (Rec-I-DCM3) and GRAPPA . <italic>COGNAC</italic>
clearly outperforms FastME in accuracy. <italic>COGNAC</italic>
–using the new DCM–also reconstructs a much more accurate tree in significantly shorter time than GRAPPA with Rec-I-DCM3.</p>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Fitch, Wm" uniqKey="Fitch W">WM Fitch</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hartigan, Ja" uniqKey="Hartigan J">JA Hartigan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
<author><name sortKey="Wyman, S" uniqKey="Wyman S">S Wyman</name>
</author>
<author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name>
</author>
<author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name>
</author>
<author><name sortKey="Yan, M" uniqKey="Yan M">M Yan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fertin, G" uniqKey="Fertin G">G Fertin</name>
</author>
<author><name sortKey="Labarre, A" uniqKey="Labarre A">A Labarre</name>
</author>
<author><name sortKey="Rusu, I" uniqKey="Rusu I">I Rusu</name>
</author>
<author><name sortKey="Tannier, E" uniqKey="Tannier E">E Tannier</name>
</author>
<author><name sortKey="Vialette, S" uniqKey="Vialette S">S Vialette</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Huson, Dh" uniqKey="Huson D">DH Huson</name>
</author>
<author><name sortKey="Nettles, Sm" uniqKey="Nettles S">SM Nettles</name>
</author>
<author><name sortKey="Warnow, Tj" uniqKey="Warnow T">TJ Warnow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Huson, Dh" uniqKey="Huson D">DH Huson</name>
</author>
<author><name sortKey="Vawter, L" uniqKey="Vawter L">L Vawter</name>
</author>
<author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Roshan, Uw" uniqKey="Roshan U">UW Roshan</name>
</author>
<author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name>
</author>
<author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
<author><name sortKey="Williams, Tl" uniqKey="Williams T">TL Williams</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Mohar, B" uniqKey="Mohar B">B Mohar</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Von Luxburg, U" uniqKey="Von Luxburg U">U von Luxburg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hendy, Md" uniqKey="Hendy M">MD Hendy</name>
</author>
<author><name sortKey="Penny, D" uniqKey="Penny D">D Penny</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bergsten, J" uniqKey="Bergsten J">J Bergsten</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
<author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name>
</author>
<author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name>
</author>
<author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lin, Y" uniqKey="Lin Y">Y Lin</name>
</author>
<author><name sortKey="Rajan, V" uniqKey="Rajan V">V Rajan</name>
</author>
<author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
<author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name>
</author>
<author><name sortKey="Wang, Ls" uniqKey="Wang L">LS Wang</name>
</author>
<author><name sortKey="Warnow, T" uniqKey="Warnow T">T Warnow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Stewart, Ca" uniqKey="Stewart C">CA Stewart</name>
</author>
<author><name sortKey="Almes, Gt" uniqKey="Almes G">GT Almes</name>
</author>
<author><name sortKey="Wheeler, Bc" uniqKey="Wheeler B">BC Wheeler</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Coghlan, A" uniqKey="Coghlan A">A Coghlan</name>
</author>
<author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name>
</author>
<author><name sortKey="Oliver, Sg" uniqKey="Oliver S">SG Oliver</name>
</author>
<author><name sortKey="Paterson, Ah" uniqKey="Paterson A">AH Paterson</name>
</author>
<author><name sortKey="Stein, L" uniqKey="Stein L">L Stein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Coghlan, A" uniqKey="Coghlan A">A Coghlan</name>
</author>
<author><name sortKey="Wolfe, Kh" uniqKey="Wolfe K">KH Wolfe</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bhutkar, A" uniqKey="Bhutkar A">A Bhutkar</name>
</author>
<author><name sortKey="Schaeffer, Sw" uniqKey="Schaeffer S">SW Schaeffer</name>
</author>
<author><name sortKey="Russo, Sm" uniqKey="Russo S">SM Russo</name>
</author>
<author><name sortKey="Xu, M" uniqKey="Xu M">M Xu</name>
</author>
<author><name sortKey="Smith, Tf" uniqKey="Smith T">TF Smith</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
<author><name sortKey="Siepel, Ac" uniqKey="Siepel A">AC Siepel</name>
</author>
<author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name>
</author>
<author><name sortKey="Liu, T" uniqKey="Liu T">T Liu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sankoff, D" uniqKey="Sankoff D">D Sankoff</name>
</author>
<author><name sortKey="El Mabrouk, N" uniqKey="El Mabrouk N">N El-Mabrouk</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bourque, G" uniqKey="Bourque G">G Bourque</name>
</author>
<author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Atteson, K" uniqKey="Atteson K">K Atteson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Saitou, N" uniqKey="Saitou N">N Saitou</name>
</author>
<author><name sortKey="Nei, M" uniqKey="Nei M">M Nei</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, G" uniqKey="Li G">G Li</name>
</author>
<author><name sortKey="Ma, J" uniqKey="Ma J">J Ma</name>
</author>
<author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pattengale, Nd" uniqKey="Pattengale N">ND Pattengale</name>
</author>
<author><name sortKey="Swenson, Km" uniqKey="Swenson K">KM Swenson</name>
</author>
<author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pothen, A" uniqKey="Pothen A">A Pothen</name>
</author>
<author><name sortKey="Simon, H" uniqKey="Simon H">H Simon</name>
</author>
<author><name sortKey="Liou, Kp" uniqKey="Liou K">KP Liou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Newman, Mej" uniqKey="Newman M">MEJ Newman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bader, Da" uniqKey="Bader D">DA Bader</name>
</author>
<author><name sortKey="Moret, Bm" uniqKey="Moret B">BM Moret</name>
</author>
<author><name sortKey="Yan, M" uniqKey="Yan M">M Yan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lin, Y" uniqKey="Lin Y">Y Lin</name>
</author>
<author><name sortKey="Moret, Bm" uniqKey="Moret B">BM Moret</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Arndt, W" uniqKey="Arndt W">W Arndt</name>
</author>
<author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bernt, M" uniqKey="Bernt M">M Bernt</name>
</author>
<author><name sortKey="Merkle, D" uniqKey="Merkle D">D Merkle</name>
</author>
<author><name sortKey="Middendorf, M" uniqKey="Middendorf M">M Middendorf</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Swenson, Km" uniqKey="Swenson K">KM Swenson</name>
</author>
<author><name sortKey="To, Y" uniqKey="To Y">Y To</name>
</author>
<author><name sortKey="Tang, J" uniqKey="Tang J">J Tang</name>
</author>
<author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wei Xu, A" uniqKey="Wei Xu A">A Wei Xu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Blanchette, M" uniqKey="Blanchette M">M Blanchette</name>
</author>
<author><name sortKey="Kunisawa, T" uniqKey="Kunisawa T">T Kunisawa</name>
</author>
<author><name sortKey="Sankoff, D" uniqKey="Sankoff D">D Sankoff</name>
</author>
</analytic>
</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="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, USA</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">21887219</article-id>
<article-id pub-id-type="pmc">3160844</article-id>
<article-id pub-id-type="publisher-id">PONE-D-11-07384</article-id>
<article-id pub-id-type="doi">10.1371/journal.pone.0022483</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject>
</subj-group>
<subj-group subj-group-type="Discipline-v2"><subject>Biology</subject>
<subj-group><subject>Computational Biology</subject>
<subj-group><subject>Genomics</subject>
<subj-group><subject>Genome Evolution</subject>
</subj-group>
</subj-group>
<subj-group><subject>Evolutionary Modeling</subject>
</subj-group>
</subj-group>
</subj-group>
<subj-group subj-group-type="Discipline-v2"><subject>Computer Science</subject>
<subj-group><subject>Algorithms</subject>
</subj-group>
<subj-group><subject>Computerized Simulations</subject>
</subj-group>
</subj-group>
</article-categories>
<title-group><article-title>Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time</article-title>
<alt-title alt-title-type="running-head">Fast Tree Reconstruction Using the Spectral Method</alt-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Kang</surname>
<given-names>Seunghwa</given-names>
</name>
<xref ref-type="aff" rid="aff1"><sup>1</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Tang</surname>
<given-names>Jijun</given-names>
</name>
<xref ref-type="aff" rid="aff2"><sup>2</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Schaeffer</surname>
<given-names>Stephen W.</given-names>
</name>
<xref ref-type="aff" rid="aff3"><sup>3</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Bader</surname>
<given-names>David A.</given-names>
</name>
<xref ref-type="aff" rid="aff4"><sup>4</sup>
</xref>
<xref ref-type="corresp" rid="cor1"><sup>*</sup>
</xref>
</contrib>
</contrib-group>
<aff id="aff1"><label>1</label>
<addr-line>School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line>
</aff>
<aff id="aff2"><label>2</label>
<addr-line>Department of Computer Science and Engineering, University of South Carolina, Columbia, South Carolina, United States of America</addr-line>
</aff>
<aff id="aff3"><label>3</label>
<addr-line>Department of Biology, The Pennsylvania State University, University Park, Pennsylvania, United States of America</addr-line>
</aff>
<aff id="aff4"><label>4</label>
<addr-line>School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, Georgia, United States of America</addr-line>
</aff>
<contrib-group><contrib contrib-type="editor"><name><surname>Schönbach</surname>
<given-names>Christian</given-names>
</name>
<role>Editor</role>
<xref ref-type="aff" rid="edit1"></xref>
</contrib>
</contrib-group>
<aff id="edit1">Kyushu Institute of Technology, Japan</aff>
<author-notes><corresp id="cor1">* E-mail: <email>bader@cc.gatech.edu</email>
</corresp>
<fn fn-type="con"><p>Conceived and designed the experiments: SK JT DB. Performed the experiments: SK. Analyzed the data: SK. Contributed reagents/materials/analysis tools: SK JT DB. Wrote the paper: SK JT SS DB. Proposed this research: JT SS DB.</p>
</fn>
</author-notes>
<pub-date pub-type="collection"><year>2011</year>
</pub-date>
<pub-date pub-type="epub"><day>24</day>
<month>8</month>
<year>2011</year>
</pub-date>
<volume>6</volume>
<issue>8</issue>
<elocation-id>e22483</elocation-id>
<history><date date-type="received"><day>29</day>
<month>4</month>
<year>2011</year>
</date>
<date date-type="accepted"><day>22</day>
<month>6</month>
<year>2011</year>
</date>
</history>
<permissions><copyright-statement>Kang et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.</copyright-statement>
<copyright-year>2011</copyright-year>
</permissions>
<abstract><p>Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious evolutionary scenario using the species' genome data. MP methods are considered to be accurate, but they are also computationally expensive especially for a large number of species. Several disk-covering methods (DCMs), which decompose the input species to multiple overlapping subgroups (or disks), have been proposed to solve the problem in a divide-and-conquer way.</p>
<p>We design a new DCM based on the spectral method and also develop the <italic>COGNAC</italic>
(Comparing Orders of Genes using Novel Algorithms and high-performance Computers) software package. <italic>COGNAC</italic>
uses the new DCM to reduce the phylogenetic tree search space and selects an output tree from the reduced search space based on the MP principle. We test the new DCM using gene order data and inversion distance. The new DCM not only reduces the number of candidate tree topologies but also excludes erroneous tree topologies which can be selected by original MP methods. Initial labeling of internal genomes affects the accuracy of MP methods using gene order data, and the new DCM enables more accurate initial labeling as well. <italic>COGNAC</italic>
demonstrates superior accuracy as a consequence. We compare <italic>COGNAC</italic>
with FastME and the combination of the state of the art DCM (Rec-I-DCM3) and GRAPPA . <italic>COGNAC</italic>
clearly outperforms FastME in accuracy. <italic>COGNAC</italic>
–using the new DCM–also reconstructs a much more accurate tree in significantly shorter time than GRAPPA with Rec-I-DCM3.</p>
</abstract>
<counts><page-count count="12"></page-count>
</counts>
</article-meta>
</front>
<body><sec id="s1"><title>Introduction</title>
<p>Maximum parsimony (MP) <xref ref-type="bibr" rid="pone.0022483-Fitch1">[1]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Hartigan1">[2]</xref>
methods enumerate candidate trees for the input species and select the most parsimonious tree as an output tree by processing the input species' genome data (such as nucleotide sequence data or gene order data). MP methods are considered to be accurate, but finding the most parsimonious tree is often computationally very expensive. Even with an efficient branch and bounding strategy and for a relatively small number of species, MP methods need to evaluate a large number of candidate tree topologies. The number becomes prohibitively large for many species.</p>
<p>Ranking different tree topologies is much more expensive for gene order data than nucleotide sequence data. For gene order data, there is no known algorithm to find the most parsimonious labeling of the internal genomes in a tree to compute the tree's parsimony score if the tree has more than three leaf genomes <xref ref-type="bibr" rid="pone.0022483-Moret1">[3]</xref>
. Even heuristics <xref ref-type="bibr" rid="pone.0022483-Fertin1">[4]</xref>
to score a topology are NP-hard assuming a linear-time computable pairwise distance metric (<italic>e.g.</italic>
breakpoint distance, inversion distance, and DCJ distance). Computing the distance between two genomes can be NP-hard as well based on the definition of distance <xref ref-type="bibr" rid="pone.0022483-Fertin1">[4]</xref>
. A large number of candidate trees is even more problematic for gene order data as a result.</p>
<p>Warnow and her group <xref ref-type="bibr" rid="pone.0022483-Huson1">[5]</xref>
–<xref ref-type="bibr" rid="pone.0022483-Roshan1">[7]</xref>
have proposed several disk-covering methods (DCMs) to reduce the candidate tree search space. DCMs decompose the input genomes to multiple overlapping disks; find a tree topology for each disk; and merge the topologies to reconstruct a tree for the entire set of input genomes. Rec-I-DCM3 <xref ref-type="bibr" rid="pone.0022483-Roshan1">[7]</xref>
, which is the most recently published DCM, recursively decomposes the input genomes to further reduce the search space and iterates the process multiple times to refine the reconstructed tree. However, existing DCMs have several shortcomings. Computing a disk decomposition is expensive for the original DCM <xref ref-type="bibr" rid="pone.0022483-Huson1">[5]</xref>
and DCM2 <xref ref-type="bibr" rid="pone.0022483-Huson2">[6]</xref>
. Rec-I-DCM3 computes a decomposition faster but requires multiple iterations to achieve high accuracy. The existing DCMs place a significant number of genomes in the overlapping region, and this also increases computing time.</p>
<p>This paper presents a new DCM that improves on existing techniques. We observe that phylogenetic tree reconstruction problems resemble graph bi-partitioning and clustering problems. Every edge in a phylogenetic tree bi-partitions the leaf genomes in the tree. A phylogenetic tree often includes multiple sets of close genomes–or clusters–as well. The spectral method <xref ref-type="bibr" rid="pone.0022483-Mohar1">[8]</xref>
, <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
, followed by heuristics to refine the initial result, is one of the most successful methods in solving graph bi-partitioning and clustering problems.</p>
<p>The new DCM is based on the spectral method and uses the pairwise distances between leaf genomes to find a disk decomposition. The spectral method computes the second smallest eigenvalue and an <inline-formula><inline-graphic xlink:href="pone.0022483.e001.jpg" mimetype="image"></inline-graphic>
</inline-formula>
eigenvector for the eigenvalue assuming <inline-formula><inline-graphic xlink:href="pone.0022483.e002.jpg" mimetype="image"></inline-graphic>
</inline-formula>
input genomes. The method initially places a genome in one partition or the other based on the sign of the corresponding eigenvector element. The magnitude of the vector element indicates the confidence level of the decision, and the new DCM uses this information to refine the initial bi-partitioning.</p>
<p>The MP principle is effective in many cases due to the strong correlation between the parsimony score of a tree topology and the topology's accuracy. However, the most parsimonious tree is not always the most accurate tree. Long branch attraction (LBA) <xref ref-type="bibr" rid="pone.0022483-Hendy1">[10]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Bergsten1">[11]</xref>
is one circumstance in which trees that seem more parsimonious can be less accurate. LBA becomes significant if a tree that best describes the phylogenetic relationships of the input species has a mix of long and short edges; if we can bi-partition the input species over a long edge in the tree, this can reduce the impact of LBA in reconstructing a sub-topology for a subset of the input genomes. If there is no long uninterrupted edge in the evolutionary history of the input species, finding an overlapping decomposition is better for accurate reconstruction. The gap between the minimum positive eigenvector element and the maximum negative eigenvector element is large if there is a long uninterrupted edge in a tree that best depicts the evolutionary history, and the new DCM exploits this information to find a close to ideal decomposition.</p>
<p>A new computer program, <italic>COGNAC</italic>
(<bold>C</bold>
omparing <bold>O</bold>
rders of <bold>G</bold>
enes using <bold>N</bold>
ovel <bold>A</bold>
lgorithms and high-performance <bold>C</bold>
omputers), recursively decomposes a disk using the new DCM till three or fewer genomes are left and builds a binary disk tree. After building a binary disk tree, <italic>COGNAC</italic>
, based on the MP principle, reconstructs sub-topologies of the leaf disks in the disk tree and recursively merges the sub-topologies to reconstruct a tree for the complete set of input genomes.</p>
<p><italic>COGNAC</italic>
uses the pairwise distances and the new DCM to reduce the candidate tree search space and uses the GRAPPA method <xref ref-type="bibr" rid="pone.0022483-Moret2">[12]</xref>
(which is based on the MP principle) to select an output tree from the reduced set of candidate tree topologies. This approach enables high accuracy in addition to fast execution time. The new DCM not only reduces the number of candidate tree topologies but also excludes erroneous tree topologies that can result from original MP methods. Initial labeling of internal genomes affects the accuracy of MP methods using gene order data, and the new DCM enables accurate initial labeling as well. We provide two examples to illustrate this in this paper using gene order data and inversion distance.</p>
<p>To experimentally evaluate <italic>COGNAC</italic>
, we use simulators (<xref ref-type="bibr" rid="pone.0022483-Tang1">[13]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Lin1">[14]</xref>
, and <xref ref-type="bibr" rid="pone.0022483-Sanderson1">[15]</xref>
) to generate model trees and apply inversion mutations based on the model trees to generate test data. We first compare <italic>COGNAC</italic>
with FastME . We use GRAPPA 's EDE <xref ref-type="bibr" rid="pone.0022483-Moret3">[16]</xref>
to correct the pairwise distances for multiple mutation events and provide the corrected distance matrix as the FastME input data. We also compare <italic>COGNAC</italic>
with the combination of Rec-I-DCM3 , the state of the art DCM, and GRAPPA <xref ref-type="bibr" rid="pone.0022483-Moret2">[12]</xref>
which is known to be one of the most accurate methods for phylogenetic tree reconstruction using gene order data. <italic>COGNAC</italic>
clearly outperforms FastME in accuracy though <italic>COGNAC</italic>
, in general, runs slower than FastME . However, considering that <italic>COGNAC</italic>
is an MP method for gene order data and FastME is a distance method, the gap in execution time is significantly smaller than typical cases. We also use the combination of Rec-I-DCM3 and GRAPPA using the FastME output tree as a guide tree, but this approach returns less accurate trees than even the FastME output tree and runs multiple orders of magnitude slower than <italic>COGNAC</italic>
. <italic>COGNAC</italic>
and data sets used in this paper are freely available from <ext-link ext-link-type="uri" xlink:href="http://code.google.com/p/cognac">http://code.google.com/p/cognac</ext-link>
in accordance with a report from an NSF funded software sustainability and reusability workshop <xref ref-type="bibr" rid="pone.0022483-Stewart1">[17]</xref>
.</p>
</sec>
<sec sec-type="methods" id="s2"><title>Methods</title>
<sec id="s2a"><title>Gene Order Data, Genome Rearrangement, Inversion Distance, GRAPPA, Median Problem, and Distance Correction</title>
<p>Assume a set of <inline-formula><inline-graphic xlink:href="pone.0022483.e003.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genes (<inline-formula><inline-graphic xlink:href="pone.0022483.e004.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) common to all the input genomes. Gene order data represent each input genome as a sequence of the <inline-formula><inline-graphic xlink:href="pone.0022483.e005.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genes. A gene in gene order data has a sign (either <inline-formula><inline-graphic xlink:href="pone.0022483.e006.jpg" mimetype="image"></inline-graphic>
</inline-formula>
or <inline-formula><inline-graphic xlink:href="pone.0022483.e007.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) based on the gene's strandedness. Genome rearrangement events reorder genes in gene order data and also change the strandedness of genes <xref ref-type="bibr" rid="pone.0022483-Coghlan1">[18]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Coghlan2">[19]</xref>
. Inversion mutations are one of the genome rearrangement events that reorganize the order of genes, and many organellar genomes as well as eukaryotic lineages (<xref ref-type="bibr" rid="pone.0022483-Coghlan1">[18]</xref>
–<xref ref-type="bibr" rid="pone.0022483-Bhutkar1">[20]</xref>
) evolve with inversion as a main evolutionary mechanism. An inversion reverses the order and the sign of genes. Assume a genome (say <inline-formula><inline-graphic xlink:href="pone.0022483.e008.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) represented by the following order of genes: <inline-formula><inline-graphic xlink:href="pone.0022483.e009.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. An inversion between the <inline-formula><inline-graphic xlink:href="pone.0022483.e010.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and the <inline-formula><inline-graphic xlink:href="pone.0022483.e011.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genes transforms <inline-formula><inline-graphic xlink:href="pone.0022483.e012.jpg" mimetype="image"></inline-graphic>
</inline-formula>
to <inline-formula><inline-graphic xlink:href="pone.0022483.e013.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. The length of an inversion is the number of genes involved in the inversion event (<inline-formula><inline-graphic xlink:href="pone.0022483.e014.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the example). The inversion distance between two genomes is the minimum number of inversions required to transform one genome to the other. A phylogenetic tree reconstructed using inversion distance is often more accurate than a tree reconstructed using breakpoint distance <xref ref-type="bibr" rid="pone.0022483-Moret4">[21]</xref>
. We refer readers to <xref ref-type="bibr" rid="pone.0022483-Fertin1">[4]</xref>
and <xref ref-type="bibr" rid="pone.0022483-Sankoff1">[22]</xref>
for further details about gene order data and genome rearrangement events.</p>
<p>GRAPPA <xref ref-type="bibr" rid="pone.0022483-Moret2">[12]</xref>
, along with MGR <xref ref-type="bibr" rid="pone.0022483-Bourque1">[23]</xref>
, is the most accurate and widely used software for reconstructing a phylogenetic tree using gene order data. GRAPPA supports inversion distance as well. GRAPPA exhaustively searches the entire candidate tree space (<inline-formula><inline-graphic xlink:href="pone.0022483.e015.jpg" mimetype="image"></inline-graphic>
</inline-formula>
unrooted tree topologies for <inline-formula><inline-graphic xlink:href="pone.0022483.e016.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes); enumerates candidate tree topologies with the branch-and-bound technique; scores the enumerated candidate tree topologies; and selects the trees with the lowest parsimony score. To score a tree topology, GRAPPA repeatedly solves median problems till the score of the topology converges. A median problem finds a median genome of three genomes, and a median genome of three genomes is a genome that minimizes the sum of distances between the genome and the three input genomes.</p>
<p>The inversion distance between two genomes saturates if the true number of inversions between the two genomes exceeds a certain threshold value–for two genomes with <inline-formula><inline-graphic xlink:href="pone.0022483.e017.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genes, the inversion distance between the two genomes cannot exceed <inline-formula><inline-graphic xlink:href="pone.0022483.e018.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. This lowers the accuracy of reconstructed trees. Common adjacencies of genes in two genomes saturate significantly later than the inversion distance between the two genomes, and GRAPPA 's EDE <xref ref-type="bibr" rid="pone.0022483-Moret3">[16]</xref>
exploits this information to estimate the true number of inversions between two genomes even after the inversion distance between the two genomes saturates.</p>
</sec>
<sec id="s2b"><title>The Spectral Method</title>
<p>The spectral method has been widely used in solving graph bi-partitioning <xref ref-type="bibr" rid="pone.0022483-Mohar1">[8]</xref>
and clustering <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
problems. Assume a graph with vertices and edges–each vertex has some computation and the weight of an edge is proportional to the amount of communication between the two vertices connected by the edge. To process the graph using a parallel computer by distributing vertices (and associated computations) to multiple computing nodes, it is important to balance the amount of computing in each computing node while minimizing the communication between two different computing nodes. Graph bi-partitioning aims to satisfy the requirement by finding a bi-partition that minimizes the sum of the edge weights between two partitions (the sum corresponds to the amount of communication) while balancing the number of vertices in each partition. The goal of clustering is to partition the input data points to multiple highly similar subgroups. Assume another graph with vertices and edges–each vertex represents a data point and an edge weight is proportional to the similarity between the two vertices. To solve a clustering problem, one needs to partition the graph with two (or more) subgroups with a large sum of the edge weights within a subgroup (to maximize the similarity) while minimizing the sum of the edge weights between two different subgroups (to minimize the similarity). The spectral method has been very successful in finding an initial solution for these problems, and we apply the method to decompose the input genomes. We briefly explain the spectral method first before presenting our algorithm in detail.</p>
<p>The spectral method first constructs a Laplacian matrix; computes the second smallest eigenvalue and an eigenvector for the eigenvalue; and bi-partitions the input data points using the eigenvector. Assume the weighted adjacency matrix <inline-formula><inline-graphic xlink:href="pone.0022483.e019.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, where <inline-formula><inline-graphic xlink:href="pone.0022483.e020.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e021.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the similarity value between the <inline-formula><inline-graphic xlink:href="pone.0022483.e022.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and the <inline-formula><inline-graphic xlink:href="pone.0022483.e023.jpg" mimetype="image"></inline-graphic>
</inline-formula>
input data points, and the similarity value can be computed using the distance between the two data points). Let <inline-formula><inline-graphic xlink:href="pone.0022483.e024.jpg" mimetype="image"></inline-graphic>
</inline-formula>
denotes the diagonal degree matrix (<inline-formula><inline-graphic xlink:href="pone.0022483.e025.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) as well. Then there are several ways to construct a Laplacian matrix using <inline-formula><inline-graphic xlink:href="pone.0022483.e026.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e027.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e028.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e029.jpg" mimetype="image"></inline-graphic>
</inline-formula>
), <inline-formula><inline-graphic xlink:href="pone.0022483.e030.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e031.jpg" mimetype="image"></inline-graphic>
</inline-formula>
), and <inline-formula><inline-graphic xlink:href="pone.0022483.e032.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e033.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) are widely used Laplacian matrices. <inline-formula><inline-graphic xlink:href="pone.0022483.e034.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is commonly used to solve graph bi-partitioning problems, while <inline-formula><inline-graphic xlink:href="pone.0022483.e035.jpg" mimetype="image"></inline-graphic>
</inline-formula>
or <inline-formula><inline-graphic xlink:href="pone.0022483.e036.jpg" mimetype="image"></inline-graphic>
</inline-formula>
can work better for clustering problems <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
; note that <inline-formula><inline-graphic xlink:href="pone.0022483.e037.jpg" mimetype="image"></inline-graphic>
</inline-formula>
maximizes the dissimilarity between two partitions while <inline-formula><inline-graphic xlink:href="pone.0022483.e038.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e039.jpg" mimetype="image"></inline-graphic>
</inline-formula>
maximizes both the similarity within a partition and the dissimilarity between different partitions <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
. An eigenvalue (say <inline-formula><inline-graphic xlink:href="pone.0022483.e040.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) and an eigenvector (say <inline-formula><inline-graphic xlink:href="pone.0022483.e041.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) of matrix <inline-formula><inline-graphic xlink:href="pone.0022483.e042.jpg" mimetype="image"></inline-graphic>
</inline-formula>
satisfies <inline-formula><inline-graphic xlink:href="pone.0022483.e043.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. To bi-partition the input genomes, the spectral method finds the second smallest eigenvalue of the Laplacian matrix and an eigenvector for the eigenvalue. The spectral method bi-partitions the input data points using the sign of the eigenvector elements; the <inline-formula><inline-graphic xlink:href="pone.0022483.e044.jpg" mimetype="image"></inline-graphic>
</inline-formula>
element of the eigenvector determines whether the <inline-formula><inline-graphic xlink:href="pone.0022483.e045.jpg" mimetype="image"></inline-graphic>
</inline-formula>
data point belongs to one partition or the other. The magnitude of an eigenvector element provides the level of confidence for the decision and a larger magnitude suggests a higher level of confidence. This information is especially valuable in finding an overlapping decomposition of the input genomes in solving our problem; we place the genomes with a small magnitude eigenvector element in the overlapping region–the specifics will be presented later in this paper. This bi-partitioning algorithm is commonly used for graph partitioning. k-means algorithm is often used instead of using the sign of eigenvector elements for clustering problems <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
. Clustering problems often partitions the input data points to more than two groups, and in this case, they use the third smallest (and larger) eigenvalues and corresponding eigenvectors in addition to an eigenvector for the second smallest eigenvalue. Our experiments show that partitioning the input genomes to more than two groups is less accurate than bi-partitioning the input genomes; thus, we focus on bi-partitioning the input genomes in this paper.</p>
</sec>
<sec id="s2c"><title>A High-level Overview of Rec-DCM-Eigen</title>
<p>This section provides a high-level informal overview of the new discovering method, Rec-DCM-Eigen, before providing an in-depth description of the algorithm. There are <inline-formula><inline-graphic xlink:href="pone.0022483.e046.jpg" mimetype="image"></inline-graphic>
</inline-formula>
possible (unrooted) topologies for <inline-formula><inline-graphic xlink:href="pone.0022483.e047.jpg" mimetype="image"></inline-graphic>
</inline-formula>
input genomes. The number grows rapidly with an increasing number of genomes or in other words, the number decreases rapidly with a decreasing number of genomes. Disk-covering methods aim to find a tree by first decomposing the entire set of input genomes to multiple subgroups; fixing a topology for each subgroup (note that the number of possible topologies for each subgroup with a smaller number genomes is much smaller than the number of possible topologies for the entire set of input genomes); and merging the topologies for the subgroups. We can apply this process recursively to further reduce the tree topology search space.</p>
<p>The effectiveness of disk-covering methods highly depends on the quality of disk decompositions. Several existing researches show that we can find an accurate tree if we can find the bi-partition over a long uninterrupted edge in the evolutionary history–see the next section for additional details. The two groups of genomes separated by a long uninterrupted edge are highly dissimilar–assuming that the similarity of two genomes is inversely proportional to the evolutionary distance between the two genomes. If we construct a fully connected graph with its vertices representing genomes and an edge weight representing the similarity between the two genomes connected by the edge, the spectral method is effective in finding a bi-partition with the high dissimilarity between two partitions; this coincides with the bi-partition over a long uninterrupted edge. However, there may not exist a long uninterrupted edge in the evolutionary history. The magnitude of eigenvector elements, which represents the confidence level of the bi-partitioning decision, becomes useful in this case. We bi-partition if the magnitude of every eigenvector element is large. If there are multiple eigenvector elements with a small magnitude value, we bi-partition excluding the genomes corresponding to the small magnitude eigenvector elements first and places the genomes with a low level of confidence in the overlapping region.</p>
<p>Recursively applying this process largely reduces the tree topology search space. This can also increase the accuracy of a reconstruction method if the tree topology search space excludes erroneous tree topologies which can be selected by suboptimal methods. The newly designed disk-covering method, Rec-DCM-Eigen, achieves this goal. <xref ref-type="fig" rid="pone-0022483-g001">Figure 1</xref>
depicts our new DCM in high-level and the remainder of this section presents details of the algorithm.</p>
<fig id="pone-0022483-g001" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g001</object-id>
<label>Figure 1</label>
<caption><title>An overview of the new DCM.</title>
</caption>
<graphic xlink:href="pone.0022483.g001"></graphic>
</fig>
</sec>
<sec id="s2d"><title>A New Disk-Covering Method Based on the Spectral Method</title>
<p>We define compatible, (incompatible but) recoverable, and irrecoverable disk decompositions first before presenting our new DCM. A disk decomposition is compatible if there was a speciation event in the evolutionary history (or if there is an edge in the model tree used for the simulation) that separates the genomes in the exclusive region of one disk from the genomes in the exclusive region of the other disk. Genomes in the overlapping region do not affect the compatibility. If a disk decomposition is incompatible but the incompatibility can be recovered in the merging step, then the disk decomposition is recoverable. See <xref ref-type="fig" rid="pone-0022483-g002">Figure 2</xref>
for an example.</p>
<fig id="pone-0022483-g002" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g002</object-id>
<label>Figure 2</label>
<caption><title>An incompatible but recoverable disk decomposition.</title>
</caption>
<graphic xlink:href="pone.0022483.g002"></graphic>
</fig>
<p>In <xref ref-type="fig" rid="pone-0022483-g002">Figure 2</xref>
, there is no edge separating A0, C1, C2, C3, and C4 from A2, A3, B2, B3, and B4; the decomposition is incompatible. Yet, if we reconstruct the correct sub-topology for each disk, we can reconstruct the correct topology for the entire set of genomes by merging the two sub-topologies without changing the sub-topologies; the decomposition is recoverable. If a decomposition is incompatible and is not recoverable, then the decomposition is irrecoverable. Our new DCM decomposes the input genomes to two disks (each disk contains a subset of the input genomes) and aims to find a compatible or at least recoverable disk decomposition.</p>
<p>If we can find the bi-partition over a long uninterrupted edge in the evolutionary history, this improves the accuracy of a reconstructed tree while reducing the tree topology search space. Atteson <xref ref-type="bibr" rid="pone.0022483-Atteson1">[24]</xref>
proved that even the computationally inexpensive neighbor-joining (NJ) method <xref ref-type="bibr" rid="pone.0022483-Saitou1">[25]</xref>
reconstructs a tree with 100% topological accuracy if the maximum gap between the additive distance (the sum of the edge lengths in the path between two genomes in a tree that best captures the evolutionary history) and the pairwise distance between two genomes in the input genomes is smaller than one half of the shortest edge in the tree to reconstruct. The gap is nearly zero for close genomes and we can reconstruct a tree with 100% topological accuracy for close genomes unless there is a very short edge in the tree. Bi-partitioning over a long edge significantly reduces the maximum pairwise distance between the genomes in each partition. Bi-partitioning over a long edge also prevents the long edge from disturbing the accurate reconstruction of the phylogeny for the genomes in the two subsets in each side of the edge <xref ref-type="bibr" rid="pone.0022483-Bergsten1">[11]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Li1">[26]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Pattengale1">[27]</xref>
. If there is a long uninterrupted edge in the evolutionary history, detecting such a signal and finding the bi-partition over the long edge is the second goal of our new DCM.</p>
<p>A good disk decomposition method needs to decompose the input genomes even when there is no long uninterrupted edge in the evolutionary history if one wishes to reconstruct a phylogenetic tree for a large number of species. If there is no long edge in the evolutionary history, however, finding a bi-partition can be error prone. Bi-partitioning over a short edge often creates a longer edge which can negatively impact the accuracy of the tree as well. In this case, placing several genomes near the partition boundary in both disks improves the accuracy of a reconstructed tree. Our new DCM aims to include genomes that are necessary for the accurate reconstruction of the phylogeny of the genomes in the exclusive regions.</p>
<sec id="s2d1"><title>Constructing a Laplacian matrix for our DCM</title>
<p>There are two questions to be answered when constructing a Laplacian matrix. The first question is about defining a similarity metric. The second question is what type of a Laplacian matrix to use. One simple way to define a similarity metric is using the inverse of a pairwise distance. von Luxburg <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
suggested using the Gaussian similarity function instead (<inline-formula><inline-graphic xlink:href="pone.0022483.e048.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, where <inline-formula><inline-graphic xlink:href="pone.0022483.e049.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the pairwise distance between the <inline-formula><inline-graphic xlink:href="pone.0022483.e050.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and the <inline-formula><inline-graphic xlink:href="pone.0022483.e051.jpg" mimetype="image"></inline-graphic>
</inline-formula>
input genomes). Using just the inverse of <inline-formula><inline-graphic xlink:href="pone.0022483.e052.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is problematic as most similarity values can have only very small values or only very large values based on the distribution of the pairwise distances. We can control the distribution of similarity values by changing <inline-formula><inline-graphic xlink:href="pone.0022483.e053.jpg" mimetype="image"></inline-graphic>
</inline-formula>
for the Gaussian similarity function, and we adopt the function and set <inline-formula><inline-graphic xlink:href="pone.0022483.e054.jpg" mimetype="image"></inline-graphic>
</inline-formula>
to <inline-formula><inline-graphic xlink:href="pone.0022483.e055.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e056.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the maximum pairwise distance between any two genomes in a disk to decompose, and we set <inline-formula><inline-graphic xlink:href="pone.0022483.e057.jpg" mimetype="image"></inline-graphic>
</inline-formula>
to 0.125 in our experiments).</p>
<p>There are several types of Laplacian matrices such as <inline-formula><inline-graphic xlink:href="pone.0022483.e058.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e059.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e060.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. <inline-formula><inline-graphic xlink:href="pone.0022483.e061.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is inappropriate. von Luxburg <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
showed that if <inline-formula><inline-graphic xlink:href="pone.0022483.e062.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is an eigenvector of <inline-formula><inline-graphic xlink:href="pone.0022483.e063.jpg" mimetype="image"></inline-graphic>
</inline-formula>
with eigenvalue <inline-formula><inline-graphic xlink:href="pone.0022483.e064.jpg" mimetype="image"></inline-graphic>
</inline-formula>
then <inline-formula><inline-graphic xlink:href="pone.0022483.e065.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is an eigenvector of <inline-formula><inline-graphic xlink:href="pone.0022483.e066.jpg" mimetype="image"></inline-graphic>
</inline-formula>
for the same eigenvalue. In other words, the eigenvector element for a genome with many close neighboring genomes has a larger magnitude with <inline-formula><inline-graphic xlink:href="pone.0022483.e067.jpg" mimetype="image"></inline-graphic>
</inline-formula>
than <inline-formula><inline-graphic xlink:href="pone.0022483.e068.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. This is undesirable for our purpose because genomes near the partition boundary should have a lower magnitude regardless of whether there are similar genomes or not. <xref ref-type="fig" rid="pone-0022483-g003">Figure 3</xref>
illustrates the point.</p>
<fig id="pone-0022483-g003" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g003</object-id>
<label>Figure 3</label>
<caption><title>An example showing an advantage of using <inline-formula><inline-graphic xlink:href="pone.0022483.e069.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e070.jpg" mimetype="image"></inline-graphic>
</inline-formula>
over <inline-formula><inline-graphic xlink:href="pone.0022483.e071.jpg" mimetype="image"></inline-graphic>
</inline-formula>
.</title>
<p>The trees above show the phylogenetic relationships of twelve genomes. The value next to a genome name is the genome's eigenvector element computed using <inline-formula><inline-graphic xlink:href="pone.0022483.e072.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(top), <inline-formula><inline-graphic xlink:href="pone.0022483.e073.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(middle), and <inline-formula><inline-graphic xlink:href="pone.0022483.e074.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(bottom), respectively.</p>
</caption>
<graphic xlink:href="pone.0022483.g003"></graphic>
</fig>
<p>In the figure, <inline-formula><inline-graphic xlink:href="pone.0022483.e075.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e076.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e077.jpg" mimetype="image"></inline-graphic>
</inline-formula>
suggest the same bi-partitioning if we bi-partition the genomes based on the sign of eigenvector elements. <inline-formula><inline-graphic xlink:href="pone.0022483.e078.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e079.jpg" mimetype="image"></inline-graphic>
</inline-formula>
also assign small magnitude values to the genomes near the partition boundary, but <inline-formula><inline-graphic xlink:href="pone.0022483.e080.jpg" mimetype="image"></inline-graphic>
</inline-formula>
assigns large magnitude values to the genomes near the partition boundary as the genomes near the boundary has many close neighbors. As we use the magnitude of the eigenvector element to decide whether to place a genome in the overlapping region or not, this is undesirable; we reject <inline-formula><inline-graphic xlink:href="pone.0022483.e081.jpg" mimetype="image"></inline-graphic>
</inline-formula>
.</p>
<p>We discard <inline-formula><inline-graphic xlink:href="pone.0022483.e082.jpg" mimetype="image"></inline-graphic>
</inline-formula>
next. <inline-formula><inline-graphic xlink:href="pone.0022483.e083.jpg" mimetype="image"></inline-graphic>
</inline-formula>
focuses on minimizing the dissimilarity between two partitions while <inline-formula><inline-graphic xlink:href="pone.0022483.e084.jpg" mimetype="image"></inline-graphic>
</inline-formula>
attempts to maximize the similarity within a partition as well <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
. <inline-formula><inline-graphic xlink:href="pone.0022483.e085.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is more desirable for many clustering problems as maximizing the similarity within a cluster is an important objective of those problems. The key objective of our disk decomposition problem is not maximizing the similarity within a partition but finding the bi-partition over a long edge. <inline-formula><inline-graphic xlink:href="pone.0022483.e086.jpg" mimetype="image"></inline-graphic>
</inline-formula>
often returns an inferior decomposition than <inline-formula><inline-graphic xlink:href="pone.0022483.e087.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in this perspective. <xref ref-type="fig" rid="pone-0022483-g004">Figure 4</xref>
provides an example.</p>
<fig id="pone-0022483-g004" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g004</object-id>
<label>Figure 4</label>
<caption><title>An example showing an advantage of using <inline-formula><inline-graphic xlink:href="pone.0022483.e088.jpg" mimetype="image"></inline-graphic>
</inline-formula>
over <inline-formula><inline-graphic xlink:href="pone.0022483.e089.jpg" mimetype="image"></inline-graphic>
</inline-formula>
.</title>
<p>The trees above show the phylogenetic relationships of five genomes. The value next to a genome name is the genome's eigenvector element computed using <inline-formula><inline-graphic xlink:href="pone.0022483.e090.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(top) and <inline-formula><inline-graphic xlink:href="pone.0022483.e091.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(bottom), respectively.</p>
</caption>
<graphic xlink:href="pone.0022483.g004"></graphic>
</fig>
<p>In the figure, <inline-formula><inline-graphic xlink:href="pone.0022483.e092.jpg" mimetype="image"></inline-graphic>
</inline-formula>
suggests the bi-partition over the longest edge while <inline-formula><inline-graphic xlink:href="pone.0022483.e093.jpg" mimetype="image"></inline-graphic>
</inline-formula>
suggests the disk decomposition that places A0 and A1 in one partition and C0 and C1 in the other. B has a very small magnitude and will be included in both disks. <inline-formula><inline-graphic xlink:href="pone.0022483.e094.jpg" mimetype="image"></inline-graphic>
</inline-formula>
suggests a better bi-partition for our purpose, and we use <inline-formula><inline-graphic xlink:href="pone.0022483.e095.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in our experiments.</p>
<p>The perturbation theory also supports the use of <inline-formula><inline-graphic xlink:href="pone.0022483.e096.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(and <inline-formula><inline-graphic xlink:href="pone.0022483.e097.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) over <inline-formula><inline-graphic xlink:href="pone.0022483.e098.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. The theory states that for a perturbed matrix (say <inline-formula><inline-graphic xlink:href="pone.0022483.e099.jpg" mimetype="image"></inline-graphic>
</inline-formula>
= <inline-formula><inline-graphic xlink:href="pone.0022483.e100.jpg" mimetype="image"></inline-graphic>
</inline-formula>
+<inline-formula><inline-graphic xlink:href="pone.0022483.e101.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e102.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is a noise free matrix and <inline-formula><inline-graphic xlink:href="pone.0022483.e103.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is a noise matrix), the error due to <inline-formula><inline-graphic xlink:href="pone.0022483.e104.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in computing an eigenvector is not significant unless the norm of <inline-formula><inline-graphic xlink:href="pone.0022483.e105.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is very large for a Laplacian matrix <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
. This is especially true for <inline-formula><inline-graphic xlink:href="pone.0022483.e106.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e107.jpg" mimetype="image"></inline-graphic>
</inline-formula>
but this does not hold for <inline-formula><inline-graphic xlink:href="pone.0022483.e108.jpg" mimetype="image"></inline-graphic>
</inline-formula>
if there are low degree vertices <xref ref-type="bibr" rid="pone.0022483-vonLuxburg1">[9]</xref>
. In our problem, the non-additivity of the pairwise distance between two genomes corresponds to noise as the gap (<inline-formula><inline-graphic xlink:href="pone.0022483.e109.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) between the ideal Laplacian matrix constructed using additive distances (<inline-formula><inline-graphic xlink:href="pone.0022483.e110.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, note that we can construct a 100% accurate topology if we can find the additive pairwise distances between the input genomes <xref ref-type="bibr" rid="pone.0022483-Atteson1">[24]</xref>
) and a Laplacian matrix constructed using computed distances (<inline-formula><inline-graphic xlink:href="pone.0022483.e111.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) increases as the pairwise distances between the input genomes become more non-additive. If we use inversion distance but the input genomes evolve via a mix of inversions and transpositions, this also increases the level of noise. <inline-formula><inline-graphic xlink:href="pone.0022483.e112.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is robust to such noise, and this also justifies the use of <inline-formula><inline-graphic xlink:href="pone.0022483.e113.jpg" mimetype="image"></inline-graphic>
</inline-formula>
over <inline-formula><inline-graphic xlink:href="pone.0022483.e114.jpg" mimetype="image"></inline-graphic>
</inline-formula>
.</p>
</sec>
<sec id="s2d2"><title>Finding a disk decomposition using an eigenvector</title>
<p>The spectral method provides a reasonable initial solution in solving graph bi-partitioning and clustering problems, but the method often requires a refinement step to find a higher quality solution for such problems <xref ref-type="bibr" rid="pone.0022483-Pothen1">[28]</xref>
, <xref ref-type="bibr" rid="pone.0022483-Newman1">[29]</xref>
. In the context of disk decomposition for phylogenetic tree reconstruction, a refinement step is necessary if there is no long edge in a tree that best captures the phylogenetic relationships of the input species. The spectral method suggests a bi-partition that has high dissimilarity between the two resulting partitions. If there is a long uninterrupted edge in the evolutionary history, the two groups of genomes in each side of the edge are highly dissimilar, and the spectral method is effective in finding the bi-partition over such a long edge. If there is no long uninterrupted edge, it is often very difficult to bi-partition the leaf genomes to two highly dissimilar subsets. In this case, bi-partitioning the input genomes based on the sign of an eigenvector element can often lead to an incompatible disk decomposition as the spectral method bi-partitions based on the weak dissimilarity signal in the input genomes. However, if we place genomes near the partition boundary in the overlapping region, the error can be recovered. An eigenvector element of a genome near the partition boundary has a small magnitude. Our DCM exploits this. It sorts the input genomes using their eigenvector element as a key; finds an initial bi-partition by placing the genomes with a negative eigenvector element in one disk and the genomes with a positive eigenvector element in the other; computes the difference between the smallest positive eigenvector element and the largest negative eigenvector element; places the genomes with a small magnitude eigenvector element in the overlapping region if the gap is smaller than a certain threshold value (say <inline-formula><inline-graphic xlink:href="pone.0022483.e115.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The algorithm visits genomes in each partition starting from the partition boundary in the sorted list until the gap between a current genome and the next genome exceeds another threshold value (say <inline-formula><inline-graphic xlink:href="pone.0022483.e116.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). All the visited genomes are placed in the overlapping region. Using <inline-formula><inline-graphic xlink:href="pone.0022483.e117.jpg" mimetype="image"></inline-graphic>
</inline-formula>
prevents placing only a subset of very close genomes in one partition. We use Intel MKL as an eigensolver. Intel MKL returns a normalized eigenvector, and <inline-formula><inline-graphic xlink:href="pone.0022483.e118.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e119.jpg" mimetype="image"></inline-graphic>
</inline-formula>
also need to be scaled based on the number of genomes in a disk to partition. For a disk with <inline-formula><inline-graphic xlink:href="pone.0022483.e120.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes, we use <inline-formula><inline-graphic xlink:href="pone.0022483.e121.jpg" mimetype="image"></inline-graphic>
</inline-formula>
for <inline-formula><inline-graphic xlink:href="pone.0022483.e122.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e123.jpg" mimetype="image"></inline-graphic>
</inline-formula>
for <inline-formula><inline-graphic xlink:href="pone.0022483.e124.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, respectively.</p>
<p>Placing too many genomes in the overlapping region is problematic as this increases the redundancy of computing. If there are two long edges separating two small groups of genomes from the remaining genomes, the algorithm described above places a large number of genomes in the overlapping region–genomes in the two small groups have large magnitude eigenvector elements and the remaining genomes have eigenvector elements close to zero. <xref ref-type="fig" rid="pone-0022483-g005">Figure 5</xref>
provides an example. A2, B0, B1, B2, B3, B4, B5, B6, B7, and C2 have an eigenvector element with a very small magnitude, but placing these genomes in the overlapping region is problematic.</p>
<fig id="pone-0022483-g005" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g005</object-id>
<label>Figure 5</label>
<caption><title>An example illustrating the necessity of a heuristic to avoid placing a large number of genomes in the overlapping region.</title>
<p>The tree above depicts the phylogenetic relationships of the input genomes and the eigenvector element computed using <inline-formula><inline-graphic xlink:href="pone.0022483.e125.jpg" mimetype="image"></inline-graphic>
</inline-formula>
follows a genome name. Two long edges separate A0 and A1 and C0 and C1 from the remaining genomes in the center. The eigenvector elements for the genomes in the center are very small.</p>
</caption>
<graphic xlink:href="pone.0022483.g005"></graphic>
</fig>
<p>In this case placing one of the two small groups (A0 and A1 or C0 and C1 in the figure) in one partition and the remaining genomes in the other is a better decomposition. To detect this, <italic>COGNAC</italic>
decomposes the two child disks (say Disk 0 and Disk 1) again. If one of the two child disks is decomposed to two non-overlapping disks (say Disk 2 and Disk 3) with one (assume Disk 2) of the two holding all the genomes in the overlapping region of Disk 0 and Disk 1, <italic>COGNAC</italic>
places the genomes in Disk 3 in one partition and the remaining genomes in the other instead of placing a large number of genomes in the overlapping region.</p>
</sec>
<sec id="s2d3"><title>The Time Complexity and the Space Complexity of the new DCM</title>
<p>To build a binary disk tree, <italic>COGNAC</italic>
computes the pairwise distances between the input genomes first and then recursively applies the new DCM. For <inline-formula><inline-graphic xlink:href="pone.0022483.e126.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes with <inline-formula><inline-graphic xlink:href="pone.0022483.e127.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genes per genome, computing the pairwise distances costs <inline-formula><inline-graphic xlink:href="pone.0022483.e128.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e129.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the time complexity of computing a pairwise distance) operations and <inline-formula><inline-graphic xlink:href="pone.0022483.e130.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(to store the input data)+<inline-formula><inline-graphic xlink:href="pone.0022483.e131.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(to store the pairwise distance matrix)+<inline-formula><inline-graphic xlink:href="pone.0022483.e132.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(<inline-formula><inline-graphic xlink:href="pone.0022483.e133.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the space complexity of a pairwise distance computation) space. <inline-formula><inline-graphic xlink:href="pone.0022483.e134.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e135.jpg" mimetype="image"></inline-graphic>
</inline-formula>
are <inline-formula><inline-graphic xlink:href="pone.0022483.e136.jpg" mimetype="image"></inline-graphic>
</inline-formula>
for inversion distance <xref ref-type="bibr" rid="pone.0022483-Bader1">[30]</xref>
; this leads to the overall time and space complexities of <inline-formula><inline-graphic xlink:href="pone.0022483.e137.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e138.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, respectively.</p>
<p>In computing a single disk decomposition for a disk with <inline-formula><inline-graphic xlink:href="pone.0022483.e139.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes, the time complexity is <inline-formula><inline-graphic xlink:href="pone.0022483.e140.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(Intel MKL <italic>dsyevr</italic>
eigensolver is the most expensive part in an asymptotic sense) and the space complexity is <inline-formula><inline-graphic xlink:href="pone.0022483.e141.jpg" mimetype="image"></inline-graphic>
</inline-formula>
. In the theoretical worst case, every disk composition can place only one genome in the two exclusive regions and all the remaining genomes in the overlapping region. In this case, the overall time complexity to build a binary disk tree becomes <inline-formula><inline-graphic xlink:href="pone.0022483.e142.jpg" mimetype="image"></inline-graphic>
</inline-formula>
+<inline-formula><inline-graphic xlink:href="pone.0022483.e143.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and the space complexity is <inline-formula><inline-graphic xlink:href="pone.0022483.e144.jpg" mimetype="image"></inline-graphic>
</inline-formula>
+<inline-formula><inline-graphic xlink:href="pone.0022483.e145.jpg" mimetype="image"></inline-graphic>
</inline-formula>
+<inline-formula><inline-graphic xlink:href="pone.0022483.e146.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(the last term to store the binary disk tree). In practice, only a small fraction of the genomes in a disk is placed in the overlapping region (and <italic>COGNAC</italic>
provides configuration parameters to control the size of the overlapping region such as <inline-formula><inline-graphic xlink:href="pone.0022483.e147.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e148.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The height of a binary disk tree is <inline-formula><inline-graphic xlink:href="pone.0022483.e149.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(instead of <inline-formula><inline-graphic xlink:href="pone.0022483.e150.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the worst case) and the size of a disk nearly halves in each decomposition in most practical cases. The <inline-formula><inline-graphic xlink:href="pone.0022483.e151.jpg" mimetype="image"></inline-graphic>
</inline-formula>
term to compute the pairwise distances takes much longer than the <inline-formula><inline-graphic xlink:href="pone.0022483.e152.jpg" mimetype="image"></inline-graphic>
</inline-formula>
term in our experiments. <italic>COGNAC</italic>
builds a binary disk tree in a few seconds or less in all the experiments in this paper while the time spent in processing the binary disk tree is highly input data dependent due to its NP-hard worst case time complexity (evaluating a single topology requires solving multiple NP-hard median problems and <italic>COGNAC</italic>
needs to evaluate multiple tree topologies to process the binary disk tree).</p>
</sec>
</sec>
<sec id="s2e"><title>Our Merging Algorithm</title>
<p>Our DCM largely reduces the tree topology search space but does not reconstruct a complete tree. Our merging algorithm fixes details–using the MP principle–to reconstruct a tree for the whole input genomes. To reconstruct a tree of the genomes in a parent disk, our code enumerates candidate tree topologies by merging the sub-topologies of the two child disks; scores those trees by solving median problems; and selects the trees with the lowest parsimony score. Our code has different merging routines for non-overlapping disks and overlapping disks.</p>
<sec id="s2e1"><title>Merging two non-overlapping disks</title>
<p>To merge two trees in two non-overlapping disks, <italic>COGNAC</italic>
first computes the pairwise distances between the genomes–both internal and leaf genomes–in one tree and the genomes in the other tree and finds the pair that minimizes the distance. <italic>COGNAC</italic>
enumerates candidate trees by connecting all the neighboring edges of the two vertices. In merging two sub-trees, our algorithm enumerates at most nine topologies unless there is a tie in the minimum distance.</p>
<p>This significantly reduces the number of topologies to be evaluated. Say if a disk with <inline-formula><inline-graphic xlink:href="pone.0022483.e153.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes is decomposed to two non-overlapping disks with <inline-formula><inline-graphic xlink:href="pone.0022483.e154.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e155.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes (<inline-formula><inline-graphic xlink:href="pone.0022483.e156.jpg" mimetype="image"></inline-graphic>
</inline-formula>
= <inline-formula><inline-graphic xlink:href="pone.0022483.e157.jpg" mimetype="image"></inline-graphic>
</inline-formula>
+<inline-formula><inline-graphic xlink:href="pone.0022483.e158.jpg" mimetype="image"></inline-graphic>
</inline-formula>
), respectively. For <inline-formula><inline-graphic xlink:href="pone.0022483.e159.jpg" mimetype="image"></inline-graphic>
</inline-formula>
genomes, we need to consider (2<inline-formula><inline-graphic xlink:href="pone.0022483.e160.jpg" mimetype="image"></inline-graphic>
</inline-formula>
−5)!! topologies with <inline-formula><inline-graphic xlink:href="pone.0022483.e161.jpg" mimetype="image"></inline-graphic>
</inline-formula>
leaf genomes per topology. With the above decomposition, we need to consider 9 or fewer topologies with <inline-formula><inline-graphic xlink:href="pone.0022483.e162.jpg" mimetype="image"></inline-graphic>
</inline-formula>
leaf genomes (unless there is a tie in the minimum distance), (2<inline-formula><inline-graphic xlink:href="pone.0022483.e163.jpg" mimetype="image"></inline-graphic>
</inline-formula>
−5)!! topologies with <inline-formula><inline-graphic xlink:href="pone.0022483.e164.jpg" mimetype="image"></inline-graphic>
</inline-formula>
leaf genomes, and (2<inline-formula><inline-graphic xlink:href="pone.0022483.e165.jpg" mimetype="image"></inline-graphic>
</inline-formula>
−5)!! topologies with <inline-formula><inline-graphic xlink:href="pone.0022483.e166.jpg" mimetype="image"></inline-graphic>
</inline-formula>
leaf genomes. Assume <inline-formula><inline-graphic xlink:href="pone.0022483.e167.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e168.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e169.jpg" mimetype="image"></inline-graphic>
</inline-formula>
are 10, 5, and 5, respectively. Without the decomposition, we need to consider 2,027,025 topologies with 10 leaf genomes. With the decomposition, we need to consider only 9 topologies with 10 leaf genomes and 2<inline-formula><inline-graphic xlink:href="pone.0022483.e170.jpg" mimetype="image"></inline-graphic>
</inline-formula>
15 topologies with 5 leaf genomes. A recursive application of the new DCM further reduces the candidate tree search space.</p>
</sec>
<sec id="s2e2"><title>Merging two overlapping disks</title>
<p>In order to merge two overlapping disks, our algorithm compares the two disks' topology for the genomes in the overlapping region. If there is a conflicting edge, our algorithm collapses the edge similar to <xref ref-type="bibr" rid="pone.0022483-Huson1">[5]</xref>
. After collapsing all the conflicting edges, our algorithm merges the two sub-trees. Then, our algorithm expands collapsed edges for every possible bifurcating scenario to enumerate candidate tree topologies. As the size of the overlapping region and the number of conflicting edges in the overlapping region increase, the candidate tree search space reduces in a slower rate. <italic>COGNAC</italic>
provides configuration parameters (<italic>e.g.</italic>
<inline-formula><inline-graphic xlink:href="pone.0022483.e171.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e172.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) to reduce the size of the overlapping region at the possible risk of lower accuracy.</p>
</sec>
</sec>
<sec id="s2f"><title>Illustrative Examples</title>
<p>Our new DCM not only reduces the number of candidate tree topologies but also excludes erroneous tree topologies which can be selected by original MP methods. The new DCM enables more accurate initial labeling as well. These improve the accuracy of <italic>COGNAC</italic>
as a consequence, and this section provides two examples to illustrate this.</p>
<p><xref ref-type="fig" rid="pone-0022483-g006">Figure 6</xref>
depicts a model tree used to generate test data and two reconstructed trees using an original MP method (the GRAPPA method) and <italic>COGNAC</italic>
. For the result, the length of an edge is identical to the inversion distance between the two genomes in each side of the edge–this is smaller than the number of inversions that happened in the edge if there is a parallel mutation within the edge. Each genome has 150 genes and inversion lengths used to generate test data follow the gamma distribution (<inline-formula><inline-graphic xlink:href="pone.0022483.e173.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and <inline-formula><inline-graphic xlink:href="pone.0022483.e174.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The original MP method returns four erroneous trees, and the figure depicts one of the four. The tree joins two long edges together, and this topology is vulnerable to long branch attraction. <italic>COGNAC</italic>
does not include the topology in the search space. Our DCM first places <inline-formula><inline-graphic xlink:href="pone.0022483.e175.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in one partition and the remaining genomes in the other partition. After reconstructing a tree for the genomes in the other partition, <italic>COGNAC</italic>
enumerates candidate trees by first finding the genome closest to A–the immediate ancestor of B is closest to A–and connecting A to the genome's three neighboring edges. No tree in the search space joins the external edges to A and D. Our DCM not only reduces the search space but also improves the accuracy by excluding many erroneous trees from the search space.</p>
<fig id="pone-0022483-g006" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g006</object-id>
<label>Figure 6</label>
<caption><title>A model tree (left) and two reconstructed trees using an original MP method (the GRAPPA method) (center) and <italic>COGNAC</italic>
(right).</title>
<p>Numbers on top of edges are edge lengths.</p>
</caption>
<graphic xlink:href="pone.0022483.g006"></graphic>
</fig>
<p>The new DCM often leads to better initialization of internal genomes as well. <xref ref-type="fig" rid="pone-0022483-g007">Figure 7</xref>
depicts a model tree adopted from <xref ref-type="fig" rid="pone-0022483-g008">Figure 8</xref>
of Bhutkar <italic>et al.</italic>
's paper <xref ref-type="bibr" rid="pone.0022483-Bhutkar1">[20]</xref>
. The paper does not provide the length of the external edge to <italic>D. willistoni</italic>
(Dwil in <xref ref-type="fig" rid="pone-0022483-g007">Figure 7</xref>
) and we set the edge length to a large number. We also scale down the edge lengths to experiment with significantly non-additive trees while limiting the execution time. We set the number of genes in each gene order data to 2000 first and reduce the number by 200 till <italic>COGNAC</italic>
or the original MP method does not finish within a practical time limit. For 1200 genes, the original MP method runs for 7.3 hours and returns two erroneous trees (one false positive and two false negatives for one tree and two false positives and two false negatives for the other tree). <italic>COGNAC</italic>
finishes in 40 milliseconds and retrieves the 100% accurate topology. The original MP method does not finish within a practical limit for 1000 or less genes. <italic>COGNAC</italic>
reconstructs the 100% accurate topology even for 800 genes (in 2.2 hours).</p>
<fig id="pone-0022483-g007" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g007</object-id>
<label>Figure 7</label>
<caption><title>A model tree used to demonstrate the superiority of <italic>COGNAC</italic>
in initializing internal nodes.</title>
<p>The figure depicts a model tree adopted from a biology paper <xref ref-type="bibr" rid="pone.0022483-Bhutkar1">[20]</xref>
.</p>
</caption>
<graphic xlink:href="pone.0022483.g007"></graphic>
</fig>
<fig id="pone-0022483-g008" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.g008</object-id>
<label>Figure 8</label>
<caption><title>A summary of the experimental results.</title>
<p>The figures plot (FP+FN)/2 (FP is the number of false positives and FN is the number of false negatives) for a varying number of genomes (20, 40, 80, 160, 320, 640). The numbers are the average of the finished computations. Missing points indicate that no computation finished within 24 hours. See <xref ref-type="table" rid="pone-0022483-t001">Tables 1</xref>
, <xref ref-type="table" rid="pone-0022483-t002">2</xref>
, <xref ref-type="table" rid="pone-0022483-t003">3</xref>
, and <xref ref-type="table" rid="pone-0022483-t004">4</xref>
for additional details.</p>
</caption>
<graphic xlink:href="pone.0022483.g008"></graphic>
</fig>
<p>This is mainly due to better initialization. If there are only a small number of evolutionary events among a set of genomes, it is often not very difficult to accurately reconstruct the evolutionary events and the ancestral genomes. If there are a large number of events among a set of genomes, reconstructing the evolutionary events and the ancestral genomes becomes much more challenging. With the new DCM, we can initialize internal genomes using closer genomes, which is generally more accurate than initializing internal genomes using distant genomes. Without the new DCM, it is difficult to find the best order to initialize the internal genomes, and the original MP method initializes the internal genomes using the three nearest leaf genomes. For example, to initialize the immediate ancestor of Dwil, the GRAPPA method finds the median genome of Dwil and two more leaf genomes (<italic>e.g.</italic>
Dmel and Dvir). <italic>COGNAC</italic>
first places Dwil in one partition and the remaining genomes in the other partition. To merge the two partitions, <italic>COGNAC</italic>
finds the genome closest to Dwil and breaks the genome's three neighboring edges to connect Dwil. At this time, all the internal genomes except for the immediate ancestor of Dwil are already initialized. <italic>COGNAC</italic>
can initialize the immediate ancestor of Dwil by finding the median genome of Dwil and the Dwil's immediate ancestor's two neighboring internal genomes. The new DCM forces to initialize the internal genomes in a desirable order which is difficult to find in the case of the original MP method.</p>
</sec>
</sec>
<sec id="s3"><title>Results and Discussion</title>
<sec id="s3a"><title>Experimental Setup</title>
<p>We test our new method using gene order data generated using various simulators and assuming inversion distance. We run our code on a system with two 2.4 GHz quad-core Intel Nehalem-EP processors (E5330) and 12 GB DRAM. <italic>COGNAC</italic>
is multi-threaded (using Intel Thread Building Block), but we configure <italic>COGNAC</italic>
to use only one core in the system to compare with other single-threaded software packages.</p>
<p>We generate model trees using simulators used in Tang and Moret's work <xref ref-type="bibr" rid="pone.0022483-Tang1">[13]</xref>
and Lin <italic>et al.</italic>
's work <xref ref-type="bibr" rid="pone.0022483-Lin1">[14]</xref>
. Tang and Moret <xref ref-type="bibr" rid="pone.0022483-Tang1">[13]</xref>
ran tests using uniform-random trees and birth-death trees in their DCM-GRAPPA paper (for birth-death trees, they used the r8s software package <xref ref-type="bibr" rid="pone.0022483-Sanderson1">[15]</xref>
developed by Sanderson). They generated trees with identical edge lengths (all the edges in a single tree have an identical edge length) of 2, 4, and 8. This is less realistic, and it is also easy to reconstruct the model tree if all the edges in a model tree have an identical edge length. We set an edge length by randomly sampling an integer number between 0 and 16 instead. We also use model trees with skewed edge length distributions (a small number of long edges and many short edges) using the simulator introduced in <xref ref-type="bibr" rid="pone.0022483-Lin1">[14]</xref>
. The simulator generates birth-death trees using the R statistics package first (using the birth-rate of 0.001 and the death rate of 0) and modifies the edge lengths to generate non-ultrametric trees. To modify an edge length, the simulator randomly samples a floating point number (say <inline-formula><inline-graphic xlink:href="pone.0022483.e176.jpg" mimetype="image"></inline-graphic>
</inline-formula>
) between −2 and 2 and multiplies <inline-formula><inline-graphic xlink:href="pone.0022483.e177.jpg" mimetype="image"></inline-graphic>
</inline-formula>
to the edge length. After modifying all the edge lengths, the simulator uniformly scales the edge lengths to generate a tree with a specific diameter. We use 1<inline-formula><inline-graphic xlink:href="pone.0022483.e178.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e179.jpg" mimetype="image"></inline-graphic>
</inline-formula>
(the number of genes in a genome, 100 in our experiments) and 2<inline-formula><inline-graphic xlink:href="pone.0022483.e180.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e181.jpg" mimetype="image"></inline-graphic>
</inline-formula>
as diameters of the generated trees. We generate leaf genomes by applying inversions to a common ancestral genome with 100 genes. The number of inversions applied in each edge is identical to the length of an edge, and the inversion lengths follow the uniform distribution. We use the generated leaf genomes as input data.</p>
<p>There are several software packages to reconstruct a phylogenetic tree for a large number of genomes using gene order data. FastME is a widely used program based on use of distance methods. Distance methods' performance depends on the quality of the input distance matrix. We use GRAPPA 's EDE to correct inversion distance to better estimate the true number of inversions happened in the evolutionary history and feed the corrected distances as FastME input data. We also test with uncorrected distances and CDCJ <xref ref-type="bibr" rid="pone.0022483-Lin2">[31]</xref>
corrected distances, but GRAPPA 's EDE produces the best results. We present the results with the EDE in this paper. FastME has several options, and we use the NJ initialization, BNNI, and SPR as this combination produces the most accurate trees in our experiments.</p>
<p>DCM2 and Rec-I-DCM3 are options for MP methods. Tang <italic>et al.</italic>
<xref ref-type="bibr" rid="pone.0022483-Tang1">[13]</xref>
presented experimental results using the combination of DCM2 and GRAPPA in their DCM-GRAPPA paper. They used trees with identical edge lengths as mentioned in the previous paragraph, and DCM-GRAPPA ran for ten hours to two days and reconstructed trees (640 leaf genomes) with approximately 10 false positives (when edge length is 2), 1 false positive (when edge length is 4), and close to 0 false positive (when edge length is 8) on average. <italic>COGNAC</italic>
reconstructs nearly 100% accurate topologies in seconds to minutes for such trees. It is easy to reconstruct an accurate tree if all the edges in a model tree have an equal length, and as DCM-GRAPPA ran much slower than <italic>COGNAC</italic>
to return less accurate trees even in this case, we do not further compare <italic>COGNAC</italic>
with DCM-GRAPPA . Instead, we compare <italic>COGNAC</italic>
with the combination of the state of the art DCM (Rec-I-DCM3) and GRAPPA . We use the FastME output trees as a guide tree for Rec-I-DCM3 . We set the maximum subset size to 8 and the iteration count to 3 in reconstructing trees using Rec-I-DCM3 . We set maximum execution time to 24 hours, and if the execution time exceeds 24 hours, we mark the computation as unfinished.</p>
</sec>
<sec id="s3b"><title>Experimental Results and Analysis</title>
<p><xref ref-type="fig" rid="pone-0022483-g008">Figure 8</xref>
summarizes experimental results for uniform-random trees with the edge lengths between 0 and 16, birth-death trees with the edge lengths between 0 and 16, birth-death trees with a skewed edge length distribution and the diameter of 1<inline-formula><inline-graphic xlink:href="pone.0022483.e182.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e183.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and birth-death trees with a skewed edge length distribution and the diameter of 2<inline-formula><inline-graphic xlink:href="pone.0022483.e184.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e185.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, respectively. See <xref ref-type="table" rid="pone-0022483-t001">Tables 1</xref>
, <xref ref-type="table" rid="pone-0022483-t002">2</xref>
, <xref ref-type="table" rid="pone-0022483-t003">3</xref>
, and <xref ref-type="table" rid="pone-0022483-t004">4</xref>
for additional details. FastME in the figure and tables represents the combination of GRAPPA 's EDE and FastME using the options described above. Rec-I-DCM3 in the figure and tables represents the combination of Rec-I-DCM3 and GRAPPA using the FastME output tree as a guide tree. If <italic>COGNAC</italic>
returns more than one tree, we randomly select one of the returned trees. FastME returns a tree with edge lengths in a floating point number. If an edge is shorter than 0.5, we consider the edge as a zero length edge in computing the topological accuracy. We count errors for only internal edges–assigning length zero for a non-zero external edge in the model tree or assigning non-zero length to a zero-length external edge in the model tree does not increase the number of false positives or false negatives.</p>
<table-wrap id="pone-0022483-t001" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.t001</object-id>
<label>Table 1</label>
<caption><title>Experimental results for uniform-random trees with the edge lengths between 0 and 16.</title>
</caption>
<alternatives><graphic id="pone-0022483-t001-1" xlink:href="pone.0022483.t001"></graphic>
<table frame="hsides" rules="groups"><colgroup span="1"><col align="left" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
</colgroup>
<thead><tr><td align="left" rowspan="1" colspan="1"></td>
<td colspan="4" align="left" rowspan="1"><italic>COGNAC</italic>
</td>
<td colspan="4" align="left" rowspan="1">FastME</td>
<td colspan="4" align="left" rowspan="1">Rec-I-DCM3</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1"><italic>N</italic>
</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">20</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">0.1</td>
<td align="left" rowspan="1" colspan="1">0.17 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.8</td>
<td align="left" rowspan="1" colspan="1">0.3</td>
<td align="left" rowspan="1" colspan="1">0.11 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1</td>
<td align="left" rowspan="1" colspan="1">2.4</td>
<td align="left" rowspan="1" colspan="1">51 m</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">40</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.5</td>
<td align="left" rowspan="1" colspan="1">0.2</td>
<td align="left" rowspan="1" colspan="1">0.51 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.6</td>
<td align="left" rowspan="1" colspan="1">0.5</td>
<td align="left" rowspan="1" colspan="1">0.099 s</td>
<td align="left" rowspan="1" colspan="1">8</td>
<td align="left" rowspan="1" colspan="1">2.88</td>
<td align="left" rowspan="1" colspan="1">6.75</td>
<td align="left" rowspan="1" colspan="1">6.8 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">80</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.8</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">4.9 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">3.1</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">0.13 s</td>
<td align="left" rowspan="1" colspan="1">2</td>
<td align="left" rowspan="1" colspan="1">8.5</td>
<td align="left" rowspan="1" colspan="1">18.5</td>
<td align="left" rowspan="1" colspan="1">3.1 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">160</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.8</td>
<td align="left" rowspan="1" colspan="1">2.1</td>
<td align="left" rowspan="1" colspan="1">19 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">7.7</td>
<td align="left" rowspan="1" colspan="1">3.5</td>
<td align="left" rowspan="1" colspan="1">0.26 s</td>
<td align="left" rowspan="1" colspan="1">1</td>
<td align="left" rowspan="1" colspan="1">9</td>
<td align="left" rowspan="1" colspan="1">22</td>
<td align="left" rowspan="1" colspan="1">7.0 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">320</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">4.1</td>
<td align="left" rowspan="1" colspan="1">3</td>
<td align="left" rowspan="1" colspan="1">1.1 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">11.5</td>
<td align="left" rowspan="1" colspan="1">5.8</td>
<td align="left" rowspan="1" colspan="1">1.8 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">640</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">8.4</td>
<td align="left" rowspan="1" colspan="1">6.6</td>
<td align="left" rowspan="1" colspan="1">3.4 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">25.1</td>
<td align="left" rowspan="1" colspan="1">11.1</td>
<td align="left" rowspan="1" colspan="1">46 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
</tbody>
</table>
</alternatives>
<table-wrap-foot><fn id="nt101"><label></label>
<p>We generate 10 model trees for a given number of genomes (<inline-formula><inline-graphic xlink:href="pone.0022483.e186.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The number of false positives (FP), the number of false negatives (FN), and the execution time (time) in a cell are the average of the finished computations (finished: the number of finished computations within 24 hours) out of 10 trials using 10 different model trees. <inline-formula><inline-graphic xlink:href="pone.0022483.e187.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e188.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e189.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the tables are hours, minutes, and seconds, respectively.</p>
</fn>
</table-wrap-foot>
</table-wrap>
<table-wrap id="pone-0022483-t002" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.t002</object-id>
<label>Table 2</label>
<caption><title>Experimental results for birth-death trees with the edge lengths between 0 and 16.</title>
</caption>
<alternatives><graphic id="pone-0022483-t002-2" xlink:href="pone.0022483.t002"></graphic>
<table frame="hsides" rules="groups"><colgroup span="1"><col align="left" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
</colgroup>
<thead><tr><td align="left" rowspan="1" colspan="1"></td>
<td colspan="4" align="left" rowspan="1"><italic>COGNAC</italic>
</td>
<td colspan="4" align="left" rowspan="1">FastME</td>
<td colspan="4" align="left" rowspan="1">Rec-I-DCM3</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1"><italic>N</italic>
</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">20</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.2</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">0.16 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.7</td>
<td align="left" rowspan="1" colspan="1">0.1</td>
<td align="left" rowspan="1" colspan="1">0.23 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">2.4</td>
<td align="left" rowspan="1" colspan="1">1.5 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">40</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.5</td>
<td align="left" rowspan="1" colspan="1">0.3</td>
<td align="left" rowspan="1" colspan="1">0.75 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.8</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">0.22 s</td>
<td align="left" rowspan="1" colspan="1">5</td>
<td align="left" rowspan="1" colspan="1">4.8</td>
<td align="left" rowspan="1" colspan="1">12.2</td>
<td align="left" rowspan="1" colspan="1">8.7 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">80</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.6</td>
<td align="left" rowspan="1" colspan="1">1</td>
<td align="left" rowspan="1" colspan="1">7.9 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">4.4</td>
<td align="left" rowspan="1" colspan="1">1.9</td>
<td align="left" rowspan="1" colspan="1">0.23 s</td>
<td align="left" rowspan="1" colspan="1">1</td>
<td align="left" rowspan="1" colspan="1">15</td>
<td align="left" rowspan="1" colspan="1">24</td>
<td align="left" rowspan="1" colspan="1">23 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">160</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.2</td>
<td align="left" rowspan="1" colspan="1">1</td>
<td align="left" rowspan="1" colspan="1">23 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">8.3</td>
<td align="left" rowspan="1" colspan="1">4.4</td>
<td align="left" rowspan="1" colspan="1">0.66 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">320</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">5.4</td>
<td align="left" rowspan="1" colspan="1">3</td>
<td align="left" rowspan="1" colspan="1">1.3 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">19</td>
<td align="left" rowspan="1" colspan="1">10.5</td>
<td align="left" rowspan="1" colspan="1">3.3 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">640</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">10.3</td>
<td align="left" rowspan="1" colspan="1">7.2</td>
<td align="left" rowspan="1" colspan="1">4.8 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">37</td>
<td align="left" rowspan="1" colspan="1">22.2</td>
<td align="left" rowspan="1" colspan="1">25 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
</tbody>
</table>
</alternatives>
<table-wrap-foot><fn id="nt102"><label></label>
<p>We generate 10 model trees for a given number of genomes (<inline-formula><inline-graphic xlink:href="pone.0022483.e190.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The number of false positives (FP), the number of false negatives (FN), and the execution time (time) in a cell are the average of the finished computations (finished: the number of finished computations within 24 hours) out of 10 trials using 10 different model trees. <inline-formula><inline-graphic xlink:href="pone.0022483.e191.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e192.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e193.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the tables are hours, minutes, and seconds, respectively.</p>
</fn>
</table-wrap-foot>
</table-wrap>
<table-wrap id="pone-0022483-t003" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.t003</object-id>
<label>Table 3</label>
<caption><title>Experimental results for birth-death trees with the diameter of 1<inline-formula><inline-graphic xlink:href="pone.0022483.e194.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e195.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and edge lengths in a skewed distribution.</title>
</caption>
<alternatives><graphic id="pone-0022483-t003-3" xlink:href="pone.0022483.t003"></graphic>
<table frame="hsides" rules="groups"><colgroup span="1"><col align="left" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
</colgroup>
<thead><tr><td align="left" rowspan="1" colspan="1"></td>
<td colspan="4" align="left" rowspan="1"><italic>COGNAC</italic>
</td>
<td colspan="4" align="left" rowspan="1">FastME</td>
<td colspan="4" align="left" rowspan="1">Rec-I-DCM3</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1"><italic>N</italic>
</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">20</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.7</td>
<td align="left" rowspan="1" colspan="1">0.7</td>
<td align="left" rowspan="1" colspan="1">0.18 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.4</td>
<td align="left" rowspan="1" colspan="1">1.4</td>
<td align="left" rowspan="1" colspan="1">0.16 s</td>
<td align="left" rowspan="1" colspan="1">9</td>
<td align="left" rowspan="1" colspan="1">2.33</td>
<td align="left" rowspan="1" colspan="1">5.11</td>
<td align="left" rowspan="1" colspan="1">1.3 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">40</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.5</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">0.21 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">1.4</td>
<td align="left" rowspan="1" colspan="1">3.2</td>
<td align="left" rowspan="1" colspan="1">0.23 s</td>
<td align="left" rowspan="1" colspan="1">9</td>
<td align="left" rowspan="1" colspan="1">5.33</td>
<td align="left" rowspan="1" colspan="1">16.2</td>
<td align="left" rowspan="1" colspan="1">5.5 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">80</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.7</td>
<td align="left" rowspan="1" colspan="1">1.1</td>
<td align="left" rowspan="1" colspan="1">0.91 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2</td>
<td align="left" rowspan="1" colspan="1">3.7</td>
<td align="left" rowspan="1" colspan="1">0.27 s</td>
<td align="left" rowspan="1" colspan="1">9</td>
<td align="left" rowspan="1" colspan="1">13.6</td>
<td align="left" rowspan="1" colspan="1">36.7</td>
<td align="left" rowspan="1" colspan="1">2.5 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">160</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">0.9</td>
<td align="left" rowspan="1" colspan="1">1.3</td>
<td align="left" rowspan="1" colspan="1">2.4 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.5</td>
<td align="left" rowspan="1" colspan="1">4.7</td>
<td align="left" rowspan="1" colspan="1">0.57 s</td>
<td align="left" rowspan="1" colspan="1">7</td>
<td align="left" rowspan="1" colspan="1">42.7</td>
<td align="left" rowspan="1" colspan="1">93.1</td>
<td align="left" rowspan="1" colspan="1">6.0 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">320</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.1</td>
<td align="left" rowspan="1" colspan="1">3.5</td>
<td align="left" rowspan="1" colspan="1">19 s</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.1</td>
<td align="left" rowspan="1" colspan="1">5.4</td>
<td align="left" rowspan="1" colspan="1">2.0 s</td>
<td align="left" rowspan="1" colspan="1">7</td>
<td align="left" rowspan="1" colspan="1">82.1</td>
<td align="left" rowspan="1" colspan="1">183</td>
<td align="left" rowspan="1" colspan="1">8.9 h</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">640</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.6</td>
<td align="left" rowspan="1" colspan="1">5.7</td>
<td align="left" rowspan="1" colspan="1">2.9 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">2.8</td>
<td align="left" rowspan="1" colspan="1">8.3</td>
<td align="left" rowspan="1" colspan="1">13 s</td>
<td align="left" rowspan="1" colspan="1">6</td>
<td align="left" rowspan="1" colspan="1">155</td>
<td align="left" rowspan="1" colspan="1">355</td>
<td align="left" rowspan="1" colspan="1">6.2 h</td>
</tr>
</tbody>
</table>
</alternatives>
<table-wrap-foot><fn id="nt103"><label></label>
<p>We generate 10 model trees for a given number of genomes (<inline-formula><inline-graphic xlink:href="pone.0022483.e196.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The number of false positives (FP), the number of false negatives (FN), and the execution time (time) in a cell are the average of the finished computations (finished: the number of finished computations within 24 hours) out of 10 trials using 10 different model trees. <inline-formula><inline-graphic xlink:href="pone.0022483.e197.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e198.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e199.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the tables are hours, minutes, and seconds, respectively. <inline-formula><inline-graphic xlink:href="pone.0022483.e200.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the number of genes in a genome, which is 100 in our experiments.</p>
</fn>
</table-wrap-foot>
</table-wrap>
<table-wrap id="pone-0022483-t004" position="float"><object-id pub-id-type="doi">10.1371/journal.pone.0022483.t004</object-id>
<label>Table 4</label>
<caption><title>Experimental results for birth-death trees with the diameter of 2<inline-formula><inline-graphic xlink:href="pone.0022483.e201.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e202.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and edge lengths in a skewed distribution.</title>
</caption>
<alternatives><graphic id="pone-0022483-t004-4" xlink:href="pone.0022483.t004"></graphic>
<table frame="hsides" rules="groups"><colgroup span="1"><col align="left" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
<col align="center" span="1"></col>
</colgroup>
<thead><tr><td align="left" rowspan="1" colspan="1"></td>
<td colspan="4" align="left" rowspan="1"><italic>COGNAC</italic>
</td>
<td colspan="4" align="left" rowspan="1">FastME</td>
<td colspan="4" align="left" rowspan="1">Rec-I-DCM3</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1"><italic>N</italic>
</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
<td align="left" rowspan="1" colspan="1">finished</td>
<td align="left" rowspan="1" colspan="1">FP</td>
<td align="left" rowspan="1" colspan="1">FN</td>
<td align="left" rowspan="1" colspan="1">time</td>
</tr>
</thead>
<tbody><tr><td align="left" rowspan="1" colspan="1">20</td>
<td align="left" rowspan="1" colspan="1">5</td>
<td align="left" rowspan="1" colspan="1">3.2</td>
<td align="left" rowspan="1" colspan="1">3.2</td>
<td align="left" rowspan="1" colspan="1">1.2 h</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">3.2</td>
<td align="left" rowspan="1" colspan="1">3.3</td>
<td align="left" rowspan="1" colspan="1">0.25 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">40</td>
<td align="left" rowspan="1" colspan="1">6</td>
<td align="left" rowspan="1" colspan="1">3.5</td>
<td align="left" rowspan="1" colspan="1">3.83</td>
<td align="left" rowspan="1" colspan="1">52 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">6.8</td>
<td align="left" rowspan="1" colspan="1">7.6</td>
<td align="left" rowspan="1" colspan="1">0.24 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">80</td>
<td align="left" rowspan="1" colspan="1">6</td>
<td align="left" rowspan="1" colspan="1">3.67</td>
<td align="left" rowspan="1" colspan="1">5</td>
<td align="left" rowspan="1" colspan="1">19 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">10.6</td>
<td align="left" rowspan="1" colspan="1">12</td>
<td align="left" rowspan="1" colspan="1">0.27 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">160</td>
<td align="left" rowspan="1" colspan="1">7</td>
<td align="left" rowspan="1" colspan="1">5.57</td>
<td align="left" rowspan="1" colspan="1">7</td>
<td align="left" rowspan="1" colspan="1">34 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">15.1</td>
<td align="left" rowspan="1" colspan="1">18.6</td>
<td align="left" rowspan="1" colspan="1">0.69 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">320</td>
<td align="left" rowspan="1" colspan="1">5</td>
<td align="left" rowspan="1" colspan="1">6.4</td>
<td align="left" rowspan="1" colspan="1">7.6</td>
<td align="left" rowspan="1" colspan="1">14 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">18</td>
<td align="left" rowspan="1" colspan="1">25</td>
<td align="left" rowspan="1" colspan="1">3.4 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
<tr><td align="left" rowspan="1" colspan="1">640</td>
<td align="left" rowspan="1" colspan="1">6</td>
<td align="left" rowspan="1" colspan="1">7.83</td>
<td align="left" rowspan="1" colspan="1">12.8</td>
<td align="left" rowspan="1" colspan="1">14 m</td>
<td align="left" rowspan="1" colspan="1">10</td>
<td align="left" rowspan="1" colspan="1">25.8</td>
<td align="left" rowspan="1" colspan="1">42.9</td>
<td align="left" rowspan="1" colspan="1">28 s</td>
<td align="left" rowspan="1" colspan="1">0</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
<td align="left" rowspan="1" colspan="1">N/A</td>
</tr>
</tbody>
</table>
</alternatives>
<table-wrap-foot><fn id="nt104"><label></label>
<p>We generate 10 model trees for a given number of genomes (<inline-formula><inline-graphic xlink:href="pone.0022483.e203.jpg" mimetype="image"></inline-graphic>
</inline-formula>
). The number of false positives (FP), the number of false negatives (FN), and the execution time (time) in a cell are the average of the finished computations (finished: the number of finished computations within 24 hours) out of 10 trials using 10 different model trees. <inline-formula><inline-graphic xlink:href="pone.0022483.e204.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e205.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e206.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the tables are hours, minutes, and seconds, respectively. <inline-formula><inline-graphic xlink:href="pone.0022483.e207.jpg" mimetype="image"></inline-graphic>
</inline-formula>
is the number of genes in a genome, which is 100 in our experiments.</p>
</fn>
</table-wrap-foot>
</table-wrap>
<p>We generate 10 model trees for each test case. The number of false positives (FP), the number of false negatives (FN), and the execution time (time) in the figure and tables are the average of the finished computations out of 10 trials using 10 different model trees. <inline-formula><inline-graphic xlink:href="pone.0022483.e208.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, <inline-formula><inline-graphic xlink:href="pone.0022483.e209.jpg" mimetype="image"></inline-graphic>
</inline-formula>
, and <inline-formula><inline-graphic xlink:href="pone.0022483.e210.jpg" mimetype="image"></inline-graphic>
</inline-formula>
in the tables are hours, minutes, and seconds, respectively.</p>
<p><italic>COGNAC</italic>
clearly outperforms FastME and Rec-I-DCM3 in accuracy. <italic>COGNAC</italic>
also consistently reconstructs accurate trees regardless of model tree types. In contrast, FastME is less accurate for birth-death trees than uniform-random trees, and FastME 's accuracy drops significantly for birth-death trees with a larger diameter and a large number of genomes. Rec-I-DCM3 fails to improve the accuracy of the input guide tree especially for trees with a skewed edge length distribution. In reconstructing trees for 640 input genomes, <italic>COGNAC</italic>
reconstrus a tree with 15 false positives and 13 false negatives in the worst case (this happens with a birth-death tree with the edge lengths between 0 and 16), while FastME returns a tree with 34 false positives and 64 false negatives (this is for a birth-death tree with the diameter of 2<inline-formula><inline-graphic xlink:href="pone.0022483.e211.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e212.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and edge lengths in a skewed distribution) and Rec-I-DCM3 retunrs a tree with 166 false positives and 384 false negatives (this is for a birth-death tree with the diameter of 1<inline-formula><inline-graphic xlink:href="pone.0022483.e213.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e214.jpg" mimetype="image"></inline-graphic>
</inline-formula>
and edge lengths in a skewed distribution, Rec-I-DCM3 fails to output any tree for a model tree with the diameter of 2<inline-formula><inline-graphic xlink:href="pone.0022483.e215.jpg" mimetype="image"></inline-graphic>
</inline-formula>
<inline-formula><inline-graphic xlink:href="pone.0022483.e216.jpg" mimetype="image"></inline-graphic>
</inline-formula>
within the time limitation) in the worst case; this shows the robustness of <italic>COGNAC</italic>
.</p>
<p><italic>COGNAC</italic>
is much faster than Rec-I-DCM3 (both are based on the MP principle) but is slower than FastME which is a distance method. The most expensive routine in both <italic>COGNAC</italic>
and Rec-I-DCM3 (in combination with GRAPPA) is a median solver. A median solver solves a median problem which finds a median genome of three genomes. The execution time to find a median genome highly depends on the distances between the three genomes. If the genomes become more distant than a certain threshold, the execution time increases very fast <xref ref-type="bibr" rid="pone.0022483-Arndt1">[32]</xref>
(note that the worst case time complexity of Caprara's median solver–both <italic>COGNAC</italic>
and GRAPPA use Caprara's median solver–is NP-hard). <italic>COGNAC</italic>
's DCM places a smaller number of genomes–often 0–in the overlapping region. <italic>COGNAC</italic>
also decomposes disks till three or fewer genomes are left while Rec-I-DCM3 requires the minimum disk size larger than a certain threshold to be accurate. Rec-I-DCM3 requires multiple iterations as well. <italic>COGNAC</italic>
needs to solve fewer median problems for closer genomes as a consequence, and this explains <italic>COGNAC</italic>
's faster execution time.</p>
<p>MP methods for gene order data generally run multiple orders of magnitude slower than distance methods. Even though <italic>COGNAC</italic>
runs slower than FastME , the difference is much less than the difference between typical MP and distance methods using gene order data. <italic>COGNAC</italic>
is reasonably fast in most cases but becomes very slow if <italic>COGNAC</italic>
needs to find a median genome of three distant genomes (<italic>COGNAC</italic>
's execution time to reconstruct a phylogenetic tree for 640 genomes varies from less than 30 seconds to over 24 hours); this is not an artifact of our newly developed DCM but a shortcoming of the median algorithm used in <italic>COGNAC</italic>
. There are faster median solvers in the literature– <italic>e.g.</italic>
<xref ref-type="bibr" rid="pone.0022483-Arndt1">[32]</xref>
–<xref ref-type="bibr" rid="pone.0022483-Swenson1">[34]</xref>
for inversion median and <xref ref-type="bibr" rid="pone.0022483-WeiXu1">[35]</xref>
for DCJ median, but even those become very slow for very distant genomes. This necessitates the development of faster median solvers.</p>
</sec>
<sec id="s3c"><title>Conclusions and Future Work</title>
<p>We design a new DCM based on the spectral method and also develop the <italic>COGNAC</italic>
software package which uses the new DCM. <italic>COGNAC</italic>
demonstrates both high accuracy and fast execution time, and our new DCM plays a significant role in <italic>COGNAC</italic>
's superior accuracy and fast execution time. The new DCM significantly reduces the candidate tree search space. If the new DCM excludes a tree that best captures the phylogenetic relationships from the search space, however, this significantly lowers the value of the new DCM. <italic>In obtaining all the results presented in the previous section, our new DCM never returns an incompatible decomposition; thus, the new DCM never excludes the model tree topology from the search space.</italic>
We perform intensive tests to find a case our new DCM returns an incompatible decomposition–we run experiments using both uniform-random trees and birth-death trees with various edge length distributions (<italic>e.g.</italic>
the average edge length of 2, 4, 8 and using various deviations from the average length) and also using manually created trees to challenge our DCM. We find our new DCM sometimes returns an incompatible decomposition–though very rarely–if the model tree of the genomes to decompose has only short edges (<italic>e.g.</italic>
if every edge has the length of 2). Even in this case, most of the incompatible decompositions are recoverable and actually recovered (if the tree has only short edges, most reasonable reconstruction methods find a very accurate tree). Our new DCM returns an irrecoverable decomposition in extremely rare cases; when the input genomes consists of multiple highly distant groups (if such groups are very distant and all the phylogenetic signals between the groups are lost, no method can reconstruct the phylogeny) or statistically very unlikely events happen (<italic>e.g.</italic>
if the model tree has only a small number of short edges but the tree has many parallel mutations). All the errors in the experimental results obtained using <italic>COGNAC</italic>
in this paper are introduced in the merging step.</p>
<p>The new DCM significantly improves the speed and accuracy of <italic>COGNAC</italic>
, but there are still remaining challenges to reconstruct accurate phylogenetic trees within a practical time limit–most importantly, finding a more accurate and flexible distance metric (than inversion distance) and designing a median solver with a bounded complexity. Especially <italic>COGNAC</italic>
currently supports only inversion and assigns the weight of 1 to every inversion regardless of their length. Ideally phylogenetic tree reconstruction software needs to support various types of chromosome-level mutations (such as inversion, translocation, transposition, fusion, fission, insertion, deletion, and duplication). Most currently available distance metrics also assign a same weight for a same type of mutations–with an exception of <xref ref-type="bibr" rid="pone.0022483-Blanchette1">[36]</xref>
. This is more due to computational efficiency rather than biological fidelity. A flexible distance metric that allows users to assign different weights based on the type and length of a mutation and possibly the significance of the genes (or other genetic markers) involved in the mutational event is highly desirable. The newly designed DCM significantly reduces the number of median problems to be solved and pairwise distances to be computed while the use of a large scale supercomputer and high-performance computing techniques can provide a much larger computing capacity; this enables us to adopt a computationally more expensive but more flexible and biologically justifiable distance metric. We will focus on addressing remaining problems by adopting new effective algorithms designed by many other researchers in the community, designing new algorithms by ourselves, and using parallel computers (including a leadership scale supercomputer) and performance optimization techniques. All these combined, <italic>COGNAC</italic>
will evolve towards a highly flexible and powerful tool to assist biologists to better understand the evolutionary history of living species using gene order data.</p>
</sec>
</sec>
</body>
<back><fn-group><fn fn-type="conflict"><p><bold>Competing Interests: </bold>
The authors have declared that no competing interests exist.</p>
</fn>
<fn fn-type="financial-disclosure"><p><bold>Funding: </bold>
This work was supported by the National Science Foundation (NSF) PetaApps project (grant numbers: NSF OCI-0904461, OCI-0904179 and OCI-0904166). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.</p>
</fn>
</fn-group>
<ref-list><title>References</title>
<ref id="pone.0022483-Fitch1"><label>1</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Fitch</surname>
<given-names>WM</given-names>
</name>
</person-group>
<year>1971</year>
<article-title>Toward defining the course of evolution: minimum change for a specific tree topology.</article-title>
<source>Systematic Zoology</source>
<volume>20</volume>
<fpage>406</fpage>
<lpage>416</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Hartigan1"><label>2</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Hartigan</surname>
<given-names>JA</given-names>
</name>
</person-group>
<year>1973</year>
<article-title>Minimum mutation fits to a given tree.</article-title>
<source>Biometrics</source>
<volume>29</volume>
<fpage>53</fpage>
<lpage>65</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Moret1"><label>3</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
<name><surname>Wyman</surname>
<given-names>S</given-names>
</name>
<name><surname>Bader</surname>
<given-names>DA</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>T</given-names>
</name>
<name><surname>Yan</surname>
<given-names>M</given-names>
</name>
</person-group>
<year>2001</year>
<article-title>A new implementation and detailed study of breakpoint analysis.</article-title>
<comment>In: Proc. Pacific Symp. on Biocomputing (PSB). Big Island, HI</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Fertin1"><label>4</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Fertin</surname>
<given-names>G</given-names>
</name>
<name><surname>Labarre</surname>
<given-names>A</given-names>
</name>
<name><surname>Rusu</surname>
<given-names>I</given-names>
</name>
<name><surname>Tannier</surname>
<given-names>E</given-names>
</name>
<name><surname>Vialette</surname>
<given-names>S</given-names>
</name>
</person-group>
<year>2009</year>
<article-title>Combinatorics of Genome Rearrange-ments.</article-title>
<comment>MIT press</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Huson1"><label>5</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Huson</surname>
<given-names>DH</given-names>
</name>
<name><surname>Nettles</surname>
<given-names>SM</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>TJ</given-names>
</name>
</person-group>
<year>1999</year>
<article-title>Disk-covering, a fast-converging method for phylogenetic tree reconstruction.</article-title>
<source>J of Computational Biology</source>
<volume>6</volume>
<fpage>369</fpage>
<lpage>386</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Huson2"><label>6</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Huson</surname>
<given-names>DH</given-names>
</name>
<name><surname>Vawter</surname>
<given-names>L</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>T</given-names>
</name>
</person-group>
<year>1999</year>
<article-title>Solving large scale phylogenetic problems using DCM2.</article-title>
<comment>In: Proc. Int'l Conf. on Intelligent Systems for Molecular Biology (ISMB). Heidelberg, Germany</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Roshan1"><label>7</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Roshan</surname>
<given-names>UW</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>T</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
<name><surname>Williams</surname>
<given-names>TL</given-names>
</name>
</person-group>
<year>2004</year>
<article-title>Rec-I-DCM3: a fast algorithmic technique for reconstructing phylogenetic trees.</article-title>
<comment>In: Proc. Computational Systems Bioinformatics Conf. (CSB). Stanford, CA</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Mohar1"><label>8</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Mohar</surname>
<given-names>B</given-names>
</name>
</person-group>
<year>1991</year>
<article-title>The Laplacian spectrum of graphs.</article-title>
<source>Graph Theory, Combinatorics, and Applications</source>
<volume>2</volume>
<fpage>871</fpage>
<lpage>898</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-vonLuxburg1"><label>9</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>von Luxburg</surname>
<given-names>U</given-names>
</name>
</person-group>
<year>2007</year>
<article-title>A tutorial on spectral clustering.</article-title>
<source>Statistics and Computing</source>
<volume>17</volume>
<fpage>395</fpage>
<lpage>416</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Hendy1"><label>10</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Hendy</surname>
<given-names>MD</given-names>
</name>
<name><surname>Penny</surname>
<given-names>D</given-names>
</name>
</person-group>
<year>1989</year>
<article-title>A framework for the quantitative study of evolutionary trees.</article-title>
<source>Systematic Zoology</source>
<volume>38</volume>
<fpage>297</fpage>
<lpage>309</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Bergsten1"><label>11</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Bergsten</surname>
<given-names>J</given-names>
</name>
</person-group>
<year>2005</year>
<article-title>A review of long-branch attraction.</article-title>
<source>Cladistics</source>
<volume>21</volume>
<fpage>163</fpage>
<lpage>193</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Moret2"><label>12</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
<name><surname>Bader</surname>
<given-names>DA</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>T</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>High-performance algorithm engineering for computational phylogenetics.</article-title>
<source>J of Supercomputing</source>
<volume>22</volume>
<fpage>99</fpage>
<lpage>111</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Tang1"><label>13</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Tang</surname>
<given-names>J</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
</person-group>
<year>2003</year>
<article-title>Scaling up accurate phylogenetic reconstruction from gene-order data.</article-title>
<source>Bioinformatics</source>
<volume>19</volume>
<fpage>305</fpage>
<lpage>312</lpage>
<pub-id pub-id-type="pmid">12538262</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Lin1"><label>14</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Lin</surname>
<given-names>Y</given-names>
</name>
<name><surname>Rajan</surname>
<given-names>V</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
</person-group>
<year>2010</year>
<article-title>Fast and accurate phylogenetic reconstruction from high-resolution whole-genome data and a novel robustness estimator.</article-title>
<comment>In: Proc. RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG). Ottawa, Canada</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Sanderson1"><label>15</label>
<element-citation publication-type="other"> <article-title>Sanderson M. r8s software package.</article-title>
<comment>Available: <ext-link ext-link-type="uri" xlink:href="http://loco.biosci.arizona.edu/r8s/">http://loco.biosci.arizona.edu/r8s/</ext-link>
</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Moret3"><label>16</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
<name><surname>Tang</surname>
<given-names>J</given-names>
</name>
<name><surname>Wang</surname>
<given-names>LS</given-names>
</name>
<name><surname>Warnow</surname>
<given-names>T</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>Steps toward accurate reconstructions of phylogenies from gene-order data.</article-title>
<source>J of Computer and System Sciences</source>
<volume>65</volume>
<fpage>508</fpage>
<lpage>525</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Stewart1"><label>17</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Stewart</surname>
<given-names>CA</given-names>
</name>
<name><surname>Almes</surname>
<given-names>GT</given-names>
</name>
<name><surname>Wheeler</surname>
<given-names>BC</given-names>
</name>
</person-group>
<year>2010</year>
<article-title>Cyberinfrastructure software sustainability and reusability: Report from an nsf funded workshop.</article-title>
<comment>Technical report, Published by Indiana University, Bloomington, IN. Available from: <ext-link ext-link-type="uri" xlink:href="http://hdl.handle.net/2022/6701">http://hdl.handle.net/2022/6701</ext-link>
</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Coghlan1"><label>18</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Coghlan</surname>
<given-names>A</given-names>
</name>
<name><surname>Eichler</surname>
<given-names>EE</given-names>
</name>
<name><surname>Oliver</surname>
<given-names>SG</given-names>
</name>
<name><surname>Paterson</surname>
<given-names>AH</given-names>
</name>
<name><surname>Stein</surname>
<given-names>L</given-names>
</name>
</person-group>
<year>2005</year>
<article-title>Chromosome evolution in eukaryotes: a multi-kingdom perspective.</article-title>
<source>TRENDS in Genetics</source>
<volume>21</volume>
<fpage>673</fpage>
<lpage>682</lpage>
<pub-id pub-id-type="pmid">16242204</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Coghlan2"><label>19</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Coghlan</surname>
<given-names>A</given-names>
</name>
<name><surname>Wolfe</surname>
<given-names>KH</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>Fourfold faster rate of genome rearrangement in Nematodes than in Drosophila.</article-title>
<source>Genome Research</source>
<volume>12</volume>
<fpage>857</fpage>
<lpage>867</lpage>
<pub-id pub-id-type="pmid">12045140</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Bhutkar1"><label>20</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Bhutkar</surname>
<given-names>A</given-names>
</name>
<name><surname>Schaeffer</surname>
<given-names>SW</given-names>
</name>
<name><surname>Russo</surname>
<given-names>SM</given-names>
</name>
<name><surname>Xu</surname>
<given-names>M</given-names>
</name>
<name><surname>Smith</surname>
<given-names>TF</given-names>
</name>
<etal></etal>
</person-group>
<year>2008</year>
<article-title>Chromosomal rearrangement inferred from comparisons of 12 Drosophila genomes.</article-title>
<source>Genetics</source>
<volume>179</volume>
<fpage>1657</fpage>
<lpage>1680</lpage>
<pub-id pub-id-type="pmid">18622036</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Moret4"><label>21</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
<name><surname>Siepel</surname>
<given-names>AC</given-names>
</name>
<name><surname>Tang</surname>
<given-names>J</given-names>
</name>
<name><surname>Liu</surname>
<given-names>T</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>Inversion medians outperform breakpoint medians in phylogeny reconstruction from gene-order data.</article-title>
<source>Lecture Note in Computer Science</source>
<volume>2452</volume>
<fpage>521</fpage>
<lpage>536</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Sankoff1"><label>22</label>
<element-citation publication-type="other"> <person-group person-group-type="author"><name><surname>Sankoff</surname>
<given-names>D</given-names>
</name>
<name><surname>El-Mabrouk</surname>
<given-names>N</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>Genome rearrangement.</article-title>
<fpage>135</fpage>
<lpage>156</lpage>
<comment>In: Current Topics in Computational Molecular Biology, MIT Press</comment>
</element-citation>
</ref>
<ref id="pone.0022483-Bourque1"><label>23</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Bourque</surname>
<given-names>G</given-names>
</name>
<name><surname>Pevzner</surname>
<given-names>PA</given-names>
</name>
</person-group>
<year>2002</year>
<article-title>Genome-scale evolution: Reconstructing gene orders in the ancestral species.</article-title>
<source>Genome Research</source>
<volume>12</volume>
<fpage>26</fpage>
<lpage>36</lpage>
<pub-id pub-id-type="pmid">11779828</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Atteson1"><label>24</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Atteson</surname>
<given-names>K</given-names>
</name>
</person-group>
<year>1999</year>
<article-title>The performance of Neighbor-Joining methods of phylogenetic reconstruction.</article-title>
<source>Algorithmica</source>
<volume>25</volume>
<fpage>251</fpage>
<lpage>278</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Saitou1"><label>25</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Saitou</surname>
<given-names>N</given-names>
</name>
<name><surname>Nei</surname>
<given-names>M</given-names>
</name>
</person-group>
<year>1987</year>
<article-title>The neighbor-joining method: a new method for reconstructing phylogenetic trees.</article-title>
<source>Molecular Biology and Evolution</source>
<volume>4</volume>
<fpage>406</fpage>
<lpage>425</lpage>
<pub-id pub-id-type="pmid">3447015</pub-id>
</element-citation>
</ref>
<ref id="pone.0022483-Li1"><label>26</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Li</surname>
<given-names>G</given-names>
</name>
<name><surname>Ma</surname>
<given-names>J</given-names>
</name>
<name><surname>Zhang</surname>
<given-names>L</given-names>
</name>
</person-group>
<year>2007</year>
<article-title>Selecting genomes for reconstruction of ancestral genomes.</article-title>
<source>Lecture Note in Computer Science</source>
<volume>4751</volume>
<fpage>110</fpage>
<lpage>121</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Pattengale1"><label>27</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Pattengale</surname>
<given-names>ND</given-names>
</name>
<name><surname>Swenson</surname>
<given-names>KM</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
</person-group>
<year>2010</year>
<article-title>Uncovering hidden phylogenetic consensus.</article-title>
<source>Lecture Note in Computer Science</source>
<volume>6053</volume>
<fpage>128</fpage>
<lpage>139</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Pothen1"><label>28</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Pothen</surname>
<given-names>A</given-names>
</name>
<name><surname>Simon</surname>
<given-names>H</given-names>
</name>
<name><surname>Liou</surname>
<given-names>KP</given-names>
</name>
</person-group>
<year>1990</year>
<article-title>Partitioning sparse matrices with eigenvectors of graphs.</article-title>
<source>SIAM J on Matrix Analysis and Applications</source>
<volume>11</volume>
<fpage>430</fpage>
<lpage>452</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Newman1"><label>29</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Newman</surname>
<given-names>MEJ</given-names>
</name>
</person-group>
<year>2006</year>
<article-title>Modularity in community structure in networks.</article-title>
<source>Proc of the National Academy of Sciences</source>
<volume>103</volume>
<fpage>8577</fpage>
<lpage>8582</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Bader1"><label>30</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Bader</surname>
<given-names>DA</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BM</given-names>
</name>
<name><surname>Yan</surname>
<given-names>M</given-names>
</name>
</person-group>
<year>2001</year>
<article-title>A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.</article-title>
<source>J of Computational Biology</source>
<volume>8</volume>
<fpage>483</fpage>
<lpage>491</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Lin2"><label>31</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Lin</surname>
<given-names>Y</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BM</given-names>
</name>
</person-group>
<year>2008</year>
<article-title>Estimating true evolutionary distances under the DCJ model.</article-title>
<source>Bioinfor-matics</source>
<volume>24</volume>
<fpage>i114</fpage>
<lpage>i122</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Arndt1"><label>32</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Arndt</surname>
<given-names>W</given-names>
</name>
<name><surname>Tang</surname>
<given-names>J</given-names>
</name>
</person-group>
<year>2007</year>
<article-title>Improving inversion median computation using commuting reversals and cycle information.</article-title>
<source>Lecture Note in Computer Science</source>
<volume>4751</volume>
<fpage>30</fpage>
<lpage>44</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Bernt1"><label>33</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Bernt</surname>
<given-names>M</given-names>
</name>
<name><surname>Merkle</surname>
<given-names>D</given-names>
</name>
<name><surname>Middendorf</surname>
<given-names>M</given-names>
</name>
</person-group>
<year>2006</year>
<article-title>Genome rearrangement based on reversals that preserve conserved intervals.</article-title>
<source>IEEE/ACM Trans Computational Biology and Bioinformatics</source>
<volume>3</volume>
<fpage>275</fpage>
<lpage>288</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Swenson1"><label>34</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Swenson</surname>
<given-names>KM</given-names>
</name>
<name><surname>To</surname>
<given-names>Y</given-names>
</name>
<name><surname>Tang</surname>
<given-names>J</given-names>
</name>
<name><surname>Moret</surname>
<given-names>BME</given-names>
</name>
</person-group>
<year>2009</year>
<article-title>Maximum independent sets of commuting and noninterfering inversions.</article-title>
<source>BMC Bioinformatics</source>
</element-citation>
</ref>
<ref id="pone.0022483-WeiXu1"><label>35</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Wei Xu</surname>
<given-names>A</given-names>
</name>
</person-group>
<year>2009</year>
<article-title>A fast and exact algorithm for the median of three problem: A graph decomposition approach.</article-title>
<source>J of Computational Biology</source>
<volume>16</volume>
<fpage>1369</fpage>
<lpage>1381</lpage>
</element-citation>
</ref>
<ref id="pone.0022483-Blanchette1"><label>36</label>
<element-citation publication-type="journal"> <person-group person-group-type="author"><name><surname>Blanchette</surname>
<given-names>M</given-names>
</name>
<name><surname>Kunisawa</surname>
<given-names>T</given-names>
</name>
<name><surname>Sankoff</surname>
<given-names>D</given-names>
</name>
</person-group>
<year>1996</year>
<article-title>Parametric genome rearrangement.</article-title>
<source>Gene</source>
<volume>172</volume>
<fpage>GC11</fpage>
<lpage>GC17</lpage>
<pub-id pub-id-type="pmid">8654963</pub-id>
</element-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000643 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000643 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= CyberinfraV1 |flux= Pmc |étape= Corpus |type= RBID |clé= |texte= }}
![]() | This area was generated with Dilib version V0.6.25. | ![]() |