Hen's teeth and whale's feet: generalized characters and their compatibility.
We propose a new model of computation for deriving phylogenetic trees based upon a generalization of qualitative characters. The model we propose is based upon recent experimental research in molecular biology. We show that the general case of determining perfect compatibility of generalized ordered characters is an NP-complete problem, but can be solved in polynomial time for a special case.
Benham
C
C
Department of Biomathematics, Mt. Sinai School of Medicine, New York, NY 10029, USA.
Kannan
S
S
Paterson
M
M
Warnow
T
T
D000465:Algorithms; D000717:Anatomy, Comparative; D000818:Animals; D002645:Chickens; D019143:Evolution, Molecular; D005528:Foot / Q000033:anatomy & histology; D016678:Genome; D006801:Humans; D008433:Mathematics; D008957:Models, Genetic; D010802:Phylogeny; D013045:Species Specificity; D014070:Tooth / Q000033:anatomy & histology; D014907:Whales