PROCEEDINGS OF THE 2002 WINTER SIMULATION CONFERENCE
PROCEEDINGS OF THE 2002 WINTER SIMULATION CONFERENCE
复制标题
DOI：
10.1109/wsc.2002.1166355
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Chun-Hung Chen;J. Snowdon;J. M. Charnes;Manchester Grand
中科院分区：
文献类型：
--
作者：
Chun-Hung Chen;J. Snowdon;J. M. Charnes;Manchester Grand
我们提出了一种新的随机方法来寻找最佳的DNA序列比对。该方法的工作原理是根据马尔可夫链生成通过图（编辑图）的随机路径。每条路径都被分配了一个分数，这些分数用于修改马尔可夫链的转移概率。该过程收敛到通过图的固定路径，对应于最佳（或接近最佳）序列比对。更新转移概率的规则基于Rubinstein的交叉熵方法，这是一种用于随机优化的新技术。这会导致非常简单和自然的更新公式。由于其通用性，数学上的易处理性和简单性，该方法具有很大的潜力，为一大类组合优化问题，特别是在生物科学。
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.