{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T05:18:10Z","timestamp":1649135890837},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"S6","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"Abstract<\/jats:title>\n \n Background<\/jats:title>\n Inference of evolutionary trees using the maximum likelihood principle is NP-hard. Therefore, all practical methods rely on heuristics. The topological transformations often used in heuristics are Nearest Neighbor Interchange (NNI), Subtree Prune and Regraft (SPR) and Tree Bisection and Reconnection (TBR). However, these topological transformations often fall easily into local optima, since there are not many trees accessible in one step from any given tree. Another more exhaustive topological transformation is p-Edge Contraction and Refinement (p-ECR). However, due to its high computation complexity, p-ECR has rarely been used in practice.<\/jats:p>\n <\/jats:sec>\n \n Results<\/jats:title>\n To make the p-ECR move more efficient, this paper proposes a new method named p-ECRNJ. The main idea of p-ECRNJ is to use neighbor joining (NJ) to refine the unresolved nodes produced in p-ECR.<\/jats:p>\n <\/jats:sec>\n \n Conclusion<\/jats:title>\n Experiments with real datasets show that p-ECRNJ can find better trees than the best known maximum likelihood methods so far and can efficiently improve local topological transforms in reasonable time.<\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/1471-2105-9-s6-s4","type":"journal-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T18:15:46Z","timestamp":1211998546000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A topological transformation in evolutionary tree search methods based on maximum likelihood combining p-ECR and neighbor joining"],"prefix":"10.1186","volume":"9","author":[{"given":"Mao-Zu","family":"Guo","sequence":"first","affiliation":[]},{"given":"Jian-Fu","family":"Li","sequence":"additional","affiliation":[]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,28]]},"reference":[{"key":"2615_CR1","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M: The neighbor-joining method: a new method for reconstructing phylogenetic Trees. Mol Biol Evol 1987, 4: 406\u2013425.","journal-title":"Mol Biol Evol"},{"key":"2615_CR2","doi-asserted-by":"publisher","first-page":"1952","DOI":"10.1093\/oxfordjournals.molbev.a004019","volume":"19","author":"Ranwez Vincent","year":"2002","unstructured":"Vincent Ranwez, Olivier Gascuel: Improvement of distance-based phylogenetic methods by a local maximum likelihood approach using triplets. Mol Biol Evol 2002, 19: 1952\u20131963.","journal-title":"Mol Biol Evol"},{"key":"2615_CR3","doi-asserted-by":"publisher","first-page":"1823","DOI":"10.1093\/oxfordjournals.molbev.a003969","volume":"18","author":"M Rosenberg","year":"2001","unstructured":"Rosenberg M, Kumar S: Traditional Phylogenetic Reconstruction Methods Reconstruct Shallow and Deep Evolutionary Relationship equally well. Mol Biol Evol 2001, 18: 1823\u20131827.","journal-title":"Mol Biol Evol"},{"key":"2615_CR4","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TCBB.2006.4","volume":"3","author":"Roch Sebastien","year":"2006","unstructured":"Sebastien Roch: A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 2006, 3: 92\u201394. 10.1109\/TCBB.2006.4","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2615_CR5","first-page":"41","volume":"10","author":"GJ Olsen","year":"1994","unstructured":"Olsen GJ, Matsuda H, Hagstrom R, Overbeek R: fastDNAml: a tool for construction of phylogenetic trees of DNA sequences using maximum likelihood. Comput Appl Biosci 1994, 10: 41\u201348.","journal-title":"Comput Appl Biosci"},{"key":"2615_CR6","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1080\/10635150390235520","volume":"52","author":"Guindon Stephane","year":"2003","unstructured":"Stephane Guindon, Olivier Gascuel: A simple, fast and accurate algorithm to estimate large phylogenies by maximum likelihood. Syst Biol 2003, 52: 696\u2013704. 10.1080\/10635150390235520","journal-title":"Syst Biol"},{"key":"2615_CR7","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1093\/bioinformatics\/bti191","volume":"21","author":"A Stamatakis","year":"2005","unstructured":"Stamatakis A, Ludwig T, Meier H: RAxML-III: a fast program for maximum likelihood-based inference of large phylogenetic trees. Bioinformatics 2005, 21: 456\u2013463. 10.1093\/bioinformatics\/bti191","journal-title":"Bioinformatics"},{"key":"2615_CR8","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1093\/oxfordjournals.molbev.a025924","volume":"15","author":"P Lewis","year":"1998","unstructured":"Lewis P: A Genetic Algorithm for Maximum Likelihood Phylogeny Inference Using Nucleotide Sequence Data. Mol Biol Evol 1998, 15: 277\u2013283.","journal-title":"Mol Biol Evol"},{"key":"2615_CR9","volume-title":"Genetic algorithm approaches for the phylogenetic analysis of large biological sequence datasets under the maximum likelihood criterion, PhD dissertation","author":"DJ Zwickl","year":"2006","unstructured":"Zwickl DJ: Genetic algorithm approaches for the phylogenetic analysis of large biological sequence datasets under the maximum likelihood criterion, PhD dissertation. Dept. of Computer science, The University of Texas, Austin; 2006."},{"key":"2615_CR10","first-page":"893","volume-title":"Proceedings of the Fifteenth ACM-SIAM Symposium on Discrete Algorithms","author":"G Ganapathy","year":"2004","unstructured":"Ganapathy G, Vijaya Ramachandran, Tandy Warnow: On contract-and-refine transformations between phylogenetic Trees. In Proceedings of the Fifteenth ACM-SIAM Symposium on Discrete Algorithms. ACM Press; 2004:893\u2013902."},{"key":"2615_CR11","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0196-6774(03)00049-X","volume":"48","author":"K St John","year":"2003","unstructured":"St John K, Warnow T, Moretand B, Vawter L: Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining. Algorithms 2003, 48: 173\u2013193. 10.1016\/S0196-6774(03)00049-X","journal-title":"Algorithms"},{"key":"2615_CR12","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1093\/oxfordjournals.molbev.a025808","volume":"14","author":"O Gascuel","year":"1997","unstructured":"Gascuel O: BioNJ: an improved version of the NJ algorithm based on a simple model of sequence data. Mol Biol Evol 1997, 14: 685\u2013695.","journal-title":"Mol Biol Evol"},{"key":"2615_CR13","first-page":"459","volume":"11","author":"K Mary Kuhner","year":"1994","unstructured":"Mary Kuhner K, Felsenstein J: A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol Biol Evol 1994, 11: 459\u2013468.","journal-title":"Mol Biol Evol"},{"key":"2615_CR14","first-page":"235","volume":"13","author":"A Rambaut","year":"1997","unstructured":"Rambaut A, Grassly NC: Seq-Gen: an application for the Monte Carlo Simulation of DNA sequence evolution along phylogenetic trees. Computer Application in Biosciences 1997, 13: 235\u2013238.","journal-title":"Computer Application in Biosciences"},{"key":"2615_CR15","doi-asserted-by":"publisher","first-page":"4338","DOI":"10.1093\/bioinformatics\/bti713","volume":"21","author":"Hordijk Wim","year":"2005","unstructured":"Wim Hordijk, Olivier Gascuel: Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood. Bioinformatics 2005, 21: 4338\u20134347. 10.1093\/bioinformatics\/bti713","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-S6-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T08:24:42Z","timestamp":1630484682000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-S6-S4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,28]]},"references-count":15,"journal-issue":{"issue":"S6","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2615"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-s6-s4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,28]]},"assertion":[{"value":"28 May 2008","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S4"}}