Constructing sequence alignments from a Markov decision model with estimated parameter values

Area of Science:

• Computational Biology
• Bioinformatics
• Operations Research

Background:

• Traditional biological sequence alignment relies on dynamic programming, which is computationally intensive for large or long sequences.
• High computational costs in memory and CPU time limit the scalability of current alignment methods.

Purpose of the Study:

• To explore the application of large-scale linear programming (LP) methods for biological sequence alignment.
• To develop a novel approach that reduces the computational burden associated with aligning extensive biological sequence datasets.

Main Methods:

• Formulating sequence alignment as a controlled Markov chain process.
• Constructing a linear programming (LP) problem to minimize the expected total alignment cost.
• Solving the LP problem using a primal-dual interior point method.

Main Results:

• Demonstrated the feasibility of using LP for sequence alignment.
• Presented alignments generated by the LP method for various cost function parameters.
• Showcased a computationally efficient alternative to dynamic programming for sequence alignment.

Conclusions:

• Linear programming offers a scalable and efficient approach to biological sequence alignment.
• The proposed Markov chain-based LP model provides a viable alternative for handling large-scale alignment tasks.
• Further exploration of cost function parameters can yield diverse and optimized alignment solutions.