Fern Hunt, NIST

TITLE: Alignment of Biological Sequences using a Markov Decision Process

ABSTRACT: We formulate the alignment process in terms of a controlled Markov chain where policies that minimize the expected total cost are used to construct a suggested alignment. We discuss the linear programming approach to finding optimal policies and show the results of a preliminary implementation. Finally, we discuss the a.s. optimality of the sample path cost when an underlying Markov chain is uniformly ergodic.