Sequence alignment by rare event simulation

Jonathan Keith, Dirk P. Kroese

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

36 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the 2002 Winter Simulation Conference
Number of pages8
Publication statusPublished - 1 Dec 2002
Externally publishedYes
EventWinter Simulation Conference 2002 - San Diego, United States of America
Duration: 8 Dec 200211 Dec 2002

Publication series

NameWinter Simulation Conference Proceedings
ISSN (Print)0275-0708


ConferenceWinter Simulation Conference 2002
Abbreviated titleWSC 2002
Country/TerritoryUnited States of America
CitySan Diego

Cite this