Title :
A polynomial algorithm for the minimum quartet inconsistency problem with O(n) quartet errors
Author :
Wu, Gang ; You, Jia-Huai ; Lin, Guohui
Author_Institution :
Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada
Abstract :
We show that for the Minimum Quartet Inconsistency problem, if the number of quartet errors is O(n), where n is the number of taxa under consideration, then it can be solved in polynomial time. This improves the previously-best algorithmic result saying that if the number of quartet errors is at most (n-3)/2 then the problem can be solved in polynomial time.
Keywords :
biology computing; evolution (biological); genetics; polynomial approximation; minimum quartet inconsistency problem; polynomial algorithm; polynomial time; quartet errors; Assembly; Availability; Data analysis; Genetics; Genomics; Joining processes; Performance analysis; Phylogeny; Polynomials; Topology;
Conference_Titel :
Computational Systems Bioinformatics Conference, 2005. Workshops and Poster Abstracts. IEEE
Print_ISBN :
0-7695-2442-7
DOI :
10.1109/CSBW.2005.14
