Constructing evolutionary trees in the presence of polymorphic characters

Most phylogenetics literature and construction methods based upon character s presume monomorphism (one state per character per species), yet polymorph ism (multiple states per character per species) is well documented in both biology and historical linguistics. In this paper we consider the problem o f inferring evolutionary trees for polymorphic characters. We show efficien t algorithms for the construction of perfect phylogenies from polymorphic d ata. These methods have been used to help construct the evolutionary tree p roposed by Warnow, Ringe, and Taylor for the Indo-European family of langua ges and presented by invitation at the National Academy of Sciences in Nove mber 1995.