Premium
Search‐based optimization
Author(s) -
Wheeler Ward C
Publication year - 2003
Publication title -
cladistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.323
H-Index - 92
eISSN - 1096-0031
pISSN - 0748-3007
DOI - 10.1111/j.1096-0031.2003.tb00378.x
Subject(s) - cladogram , character (mathematics) , heuristic , sequence (biology) , phylogenetic tree , mathematical optimization , mathematics , state (computer science) , optimization problem , point (geometry) , computer science , algorithm , biology , cladistics , genetics , geometry , gene
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.