DocumentCode
2526991
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
fYear
2005
fDate
8-11 Aug. 2005
Firstpage
55
Lastpage
56
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Systems Bioinformatics Conference, 2005. Workshops and Poster Abstracts. IEEE
Print_ISBN
0-7695-2442-7
Type
conf
DOI
10.1109/CSBW.2005.14
Filename
1540538
Link To Document