Constructing sequence alignments from a Markov decision model with estimated parameter values.
Current methods for aligning biological sequences are based on dynamic programming algorithms. If large numbers of sequences or a number of long sequences are to be aligned, the required computations are expensive in memory and central processing unit (CPU) time. In an attempt to bring the tools of large-scale linear programming (LP) methods to bear on this problem, we formulate the alignment process as a controlled Markov chain and construct a suggested alignment based on policies that minimise the expected total cost of the alignment. We discuss the LP associated with the total expected discounted cost and show the results of a solution of the problem based on a primal-dual interior point method. Model parameters, estimated from aligned sequences, along with cost function parameters are used to construct the objective and constraint conditions of the LP problem. This article concludes with a discussion of some alignments obtained from the LP solutions of problems with various cost function parameter values.
Hunt
Fern Y
FY
Mathematical and Computational Sciences Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA. hunt@nist.gov
Kearsley
Anthony J
AJ
O'Gallagher
Agnes
A
D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D008390:Markov Chains; D015233:Models, Statistical; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated; D011382:Programming, Linear; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid