The problem of finding a phylogeny with maximum parsimony is one of the
main problems in computational biology. While it is impossible to
search the possible tree space exhaustively for large data sets, most
heuristic approaches try to search in the neighborhood of sub-optimal
trees.
The speed of computing a score for each tree (e.g. tree length or total
number of character changes)
is as important as the
different tree search strategies. Some techniques include short-cuts
that have not been proven to be exact, and an incremental character
optimization approach by which the speedup gains
depends on data sets and is hardly
analyzed in theory.
This paper describes an exact and fast
algorithm to compute tree length and our algorithm can obtain great
speedup for any data sets.
We discuss the algorithm for
Fitch-parsimony, but it can also be applied to Wagner-parsimony.
Publication
History
Versions
of this paper appeared as:
M. Yan and D.A. Bader, ``Fast Character Optimization in Parsimony Phylogeny Reconstruction,'' Technical Report, 2003.
