Parametric analysis for ungapped Markov models of evolution
Balaji Venkatachalam · 2005
We present efficient sensitivity- analysis algorithms for two problems involving Markov models of sequence evolution: ancestral reconstruction in evolutionary trees and local ungapped alignment under log- odds scoring. Our algorithms generate complete descriptions of the optimum solutions for all possible values of the evolutionary distance. The running time of these algorithms are comparable to the running time of the algorithms for a fixed parameter value. The running time for the parametric ancestral reconstruction problem under the Kimura 2-parameter model is O(kn + kn[superscript 2/3] log k), where n is the number of sequences and k is their length, assuming all edges have the same length. For the parametric gapless alignment problem under the Jukes- Cantor model, the running time is O(mn + mn[superscript 2/3]log m), where m and n are the sequence lengths and n [less than or equal to] m.