CHAPTER 26
HEURISTIC METHODS FOR PHYLOGENETIC RECONSTRUCTION WITH MAXIMUM PARSIMONY
In this chapter, we explain how metaheuristics like local search, genetic, and memetic algorithms are used for phylogenetic reconstruction using maximum parsimony. We review some main concepts used to improve the search of a good solution that are inherited from the operational research and combinatorial optimization communities.
26.1 INTRODUCTION
Maximum parsimony (MP) is a character-based approach that relies on the work of the german entomologist Willy Hennig (1913–1976). Although Hennig’s work has generated significant controversy, the principles that underlie what was later called cladistics laid the basis for a convenient and powerful method for the analysis of molecular data with the use of computers. For more details about the early history of MP methods, see [9] (p. 136).
Cladistics, also referred to as phylogenetic systematics, can be viewed as a philosophy of classification that arranges organisms only by their order of branching in an evolutionary tree. The leaves of the tree are labeled with the operational taxonomic unit (OTU) of the problem also called taxa (singular: taxon). Ideally, the trees (or cladograms) that result from an MP analysis show the evolution of synapomorphies (derived character states inherited from the most common ancestor) between species. Many different cladograms can exist for a given set of taxa, but the ...
