A Model of Indel Evolution by Finite-State, Continuous-Time Machines

Area of Science:

• Computational Biology
• Bioinformatics
• Sequence Analysis

Background:

• Continuous-time insertion-deletion models are crucial for sequence analysis.
• Existing approximation methods for transition probabilities have limitations.

Purpose of the Study:

• To develop a systematic method for approximating finite-time transition probabilities in continuous-time insertion-deletion models.
• To improve the accuracy and applicability of sequence alignment models.

Main Methods:

• Utilizing automata theory to represent evolutionary generators and alignment distributions via pair hidden Markov models (HMMs).
• Implementing a coarse-graining operation to manage state space complexity.
• Deriving ordinary differential equations for transition probabilities and solving them via numerical integration.

Main Results:

• The proposed method provides a better fit over a broader range of parameters compared to previous approximations.
• The TKF91 model is an exact solution for single-residue indels.
• A related approach for estimating indel rates using expectation maximization is proposed.

Conclusions:

• The developed method offers a more accurate and robust approach for approximating insertion-deletion models in sequence analysis.
• This work provides a foundation for improved sequence alignment and evolutionary rate estimation.