Searching for Phylogenetic Trees under the Frequency Parsimony Criterion: An Approximation Using Generalized Parsimony

lelic frequency change as measured by the Manhattan metric. We provided three pri? mary arguments for choosing our method over other parsimony methods proposed for polymorphic data: (1) it accommodates polymorphism without resorting to coding strategies that permit the existence of im? possible conditions (e.g., ancestral loci for which all allele frequencies are zero); (2) it reduces the impact of sampling error (e.g., the failure to detect rare alleles in some populations or taxa; see also Rannala, 1995); and (3) it makes use of potentially useful frequency information that is lost in presence/absence coding strategies. De? spite its theoretical advantages, our meth? od has not been widely used because of its computational intensity and the inadequa? cy of the tree-searching algorithm used in the only existing implementation (FREQPARS; Swofford and Berlocher, 1987). Here, we propose a modification of the original method that overcomes these lim? itations by using an approximation to the original optimality criterion. In our original paper, we suggested that the MANAD (Manhattan distance, additiv? ity requirement) criterion be used to select optimal trees. Tree length is defined as the sum of the branch lengths (edges), where each branch length is measured by a Man? hattan distance. For a single brandi bound? ed by nodes A and B and a single locus ;, this distance D is defined as where p^nd p^are the frequencies of the /th allele at nodes A and B, respectively (nodes may either be terminal nodes rep? resenting terminal taxa or internal nodes representing hypothetical ancestors), and K is the total number of alleles. Obtaining a most-parsimonious reconstruction (MPR; Swofford and Maddison, 1987) under MANAD for a tree T requires finding the set of ancestral allele frequency arrays for all loci that minimize the length L of the tree. Thus,