Parametric Analysis for Ungapped Markov Models of Evolution

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 for the parametric ancestral reconstruction problem under the Kimura 2-parameter model is O(kn + kn2/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 + mn2/3 log m), where m and n are the sequence lengths and n ≤ m.