title: Search-based optimization.
abstract: The problem of determining the minimum cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete (Wang and Jiang, 1994). Traditionally, point estimations of hypothetical ancestral sequences have been used to gain heuristic, upper bounds on cladogram cost. These include procedures with such diverse approaches as non-additive optimization of multiple sequence alignment, direct optimization (Wheeler, 1996), and fixed-state character optimization (Wheeler, 1999). A method is proposed here which, by extending fixed-state character optimization, replaces the estimation process with a search. This form of optimization examines a diversity of potential state solutions for cost-efficient hypothetical ancestral sequences and can result in greatly more parsimonious cladograms. Additionally, such an approach can be applied to other NP-complete phylogenetic optimization problems such as genomic break-point analysis.
authors.affiliation: Division of Invertebrate Zoology, American Museum of Natural History, New York, NY 10024-5192, USA. wheeler@amnh.org
authors.forename: Ward C
authors.initials: WC
authors.lastname: Wheeler
mesh_terms: D000818:Animals; D001181:Arthropods / Q000145:classification* / Q000235:genetics; D001483:Base Sequence; D008432:Mathematical Computing; D010163:Paleontology / Q000706:statistics & numerical data; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software