Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability. | Algorithms for Molecular Biology BioMed Central Research Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability Gang Wu 1 Ming-Yang Kao 2 Guohui Lin1 and Jia-Huai You1 Address Department of Computing Science University of Alberta Edmonton Alberta T6G 2E8 Canada and 2Department of Electrical Engineering and Computer Science Northwestern University Evanston IL 60208 USA Email Gang Wu - wgang@ Ming-Yang Kao - kao@ Guohui Lin - ghlin@ Jia-Huai You - you@ Corresponding authors Open Access Published 24 January 2008 Received 14 November 2006 Algorithms for Molecular Biology 2008 3 1 doi l748-7l88-3-l Accepted 24 January 2008 This article is available from http content 3 l l 2008 Wu et al licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License http licenses by which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. Abstract Background In recent years quartet-based phylogeny reconstruction methods have received considerable attentions in the computational biology community. Traditionally the accuracy of a phylogeny reconstruction method is measured by simulations on synthetic datasets with known true phylogenies while little theoretical analysis has been done. In this paper we present a new model-based approach to measuring the accuracy of a quartet-based phylogeny reconstruction method. Under this model we propose three efficient algorithms to reconstruct the true phylogeny with a high success probability. Results The first algorithm can reconstruct the true phylogeny from the input quartet topology set without quartet errors in O n2 time by querying at most n - 4 log n - l quartet topologies where n is the number of the taxa. When the input quartet topology set contains errors the .
