0028-825X933103-0239 $2.500 The Royal Society of New Zealand 1993 Constructing phylogeneti.pdf

New Zealand Journal of Botany, 1993, Vol. 31: 239-248 0028-825X/93/3103-0239 $2.50/0 ? The Royal Society of New Zealand 1993 239 Constructing phylogenetic trees efficiently using compatibility criteria TANDY J. WARNOW Sandia National Laboratories P.O. Box 5800 Albuquerque, NM 87185, U.S.A.* ?Present address: Department of Computer and Information Sciences, University of Pennsylvania, 200 S 33rd Street, Moore 276, Philadelphia, PA 19104, U.S.A. Abstract The Character Compatibility Problem is a classical problem in computational biology concerned with constructing phylogenetic trees of minimum possible evolution from qualitative character sets. This problem arose in the 1970s, and until recently the only cases for which efficient algorithms were found were for binary (i.e. two- state) characters and for two characters at a time, while the complexity of the general problem remained open. In this paper we will discuss the remarkable progress on this problem since 1990. Keywords evolution; algorithms; phylogenetic tree; INTRODUCTION The Character Compatibility Problem is a classical problem in computational biology, which seeks to construct a phylogenetic tree of minimum possible evolution for an input species set, described by qualitative characters. Such a phylogeny is said to be perfect, and thus the problem of whether such a phylogeny exists is called both the Perfect Phylogeny Problem and the Character Compatibility Problem. We begin with the section Basic concepts from computer science. In this section we will define what we mean by the complexity of an algorithm or B93007 Received 19 January 1993; accepted 8 June 1993 problem, so that the meaning of efficient is clear, and the consequences of saying that a problem is NP-hard is also understood. We continue by defining the Character Compatibilty Problem in the section The Character Compatibility Problem, and describe the history of the problem in the section History of the Character Compatibility Problem. We discus