TY - GEN
T1 - Sequence alignment by rare event simulation
AU - Keith, Jonathan
AU - Kroese, Dirk P.
PY - 2002/12/1
Y1 - 2002/12/1
N2 - We present a new stochastic method for finding the optimal alignment of DNA sequences. The method works by generating random paths through a graph (the edit graph) according to a Markov chain. Each path is assigned a score, and these scores are used to modify the transition probabilities of the Markov chain. This procedure converges to a fixed path through the graph, corresponding to the optimal (or near-optimal) sequence alignment. The rules with which to update the transition probabilities are based on Rubinstein's Cross-Entropy Method, a new technique for stochastic optimization. This leads to very simple and natural updating formulas. Due to its versatility, mathematical tractability and simplicity, the method has great potential for a large class of combinatorial optimization problems, in particular in biological sciences.
AB - We present a new stochastic method for finding the optimal alignment of DNA sequences. The method works by generating random paths through a graph (the edit graph) according to a Markov chain. Each path is assigned a score, and these scores are used to modify the transition probabilities of the Markov chain. This procedure converges to a fixed path through the graph, corresponding to the optimal (or near-optimal) sequence alignment. The rules with which to update the transition probabilities are based on Rubinstein's Cross-Entropy Method, a new technique for stochastic optimization. This leads to very simple and natural updating formulas. Due to its versatility, mathematical tractability and simplicity, the method has great potential for a large class of combinatorial optimization problems, in particular in biological sciences.
UR - http://www.scopus.com/inward/record.url?scp=0036927460&partnerID=8YFLogxK
M3 - Conference Paper
AN - SCOPUS:0036927460
VL - 1
T3 - Winter Simulation Conference Proceedings
SP - 320
EP - 327
BT - Proceedings of the 2002 Winter Simulation Conference
T2 - Winter Simulation Conference 2002
Y2 - 8 December 2002 through 11 December 2002
ER -