Title :
A linear programming based algorithm for multiple sequence alignments
Author :
Hunt, Fern Y. ; Kearsley, Anthony J. ; Gallagher, Agnes O.
Author_Institution :
Math. & Computational Sci. Div., Nat. Inst. of Stand. & Technol., Gaithersburg, MD, USA
Abstract :
In this brief paper we discuss an approach to multiple sequence alignment based on treating the alignment process as a stochastic control problem. The use of a model based on a Markov decision process leads to a linear programming problem whose solution is linked to a suggested alignment. Our goal is to avoid the expense in time and computation encountered when dynamic programming based algorithms are used to align a large number of sequences. The dual linear programming problem can also be defined. We implemented the method on a set of cytochrome p450 sequences and compared our suggested alignments of 3 sequences with that obtained by CLUSTALW.
Keywords :
Markov processes; biology computing; dynamic programming; linear programming; physiological models; stochastic processes; CLUSTALW; Markov decision process; computation encountering; cytochrome p450 sequences; dual linear programming problem; dynamic programming; multiple sequence alignment; stochastic control problem; Costs; Dynamic programming; Heuristic algorithms; History; Large-scale systems; Linear programming; NIST; Sequences; Stochastic processes; Time measurement;
Conference_Titel :
Bioinformatics Conference, 2003. CSB 2003. Proceedings of the 2003 IEEE
Print_ISBN :
0-7695-2000-6
DOI :
10.1109/CSB.2003.1227398
