`A PHASE TRANSITION FOR THE SCORE IN MATCHING RANDOM SEQUENCES ALLOWING DELETIONS
`A PHASE TRANSITION FOR THE SCORE IN MATCHING RANDOM SEQUENCES ALLOWING DELETIONS
复制标题
DOI：
10.1214/aoap/1177005208
复制
发表时间：
1994-02-01
影响因子：
1.8
通讯作者：
Waterman, Michael S.
中科院分区：
文献类型：
--
作者：
Arratia, Richard;Waterman, Michael S.
我们考虑了一个序列匹配问题，涉及连续子序列的最优对齐分数，奖励匹配和惩罚删除和不匹配。生物学家用这个分数来比较DNA对或蛋白质序列。我们证明了对于两个长度为n的序列，当n ->∞时，当惩罚参数较小时，在n中存在线性增长，当惩罚参数较大时，在n中存在对数增长的相变。结果对具有iid或马尔可夫字母的独立序列有效。证明这一点的关键步骤是推导出与缺失匹配的大偏差结果。Chvatal和Sankoff的最长公共子序列问题是我们的设置的一个特殊情况。大偏差结果的证明利用了Azuma-Hoeffding引理。相变也建立了更一般的评分方案，允许一般的字母对字母对齐惩罚和块删除惩罚。给出了将有界增量鞅方法应用于马尔可夫过程的Lipschitz泛函的一般方法。相变适用于匹配的马尔可夫链和单一序列中的非重叠重复。
We consider a sequence matching problem involving the optimal alignment score for contiguous subsequences, rewarding matches and penalizing for deletions and mismatches. This score is used by biologists comparing pairs of DNA or protein sequences. We prove that for two sequences of length n, as n -> infinity, there is a phase transition between linear growth in n, when the penalty parameters are small, and logarithmic growth in n, when the penalties are large. The results are valid for independent sequences with iid or Markov letters. The crucial step in proving this is to derive a large deviation result for matching with deletions. The longest common subsequence problem of Chvatal and Sankoff is a special case of our setup. The proof of the large deviation result exploits the Azuma-Hoeffding lemma. The phase transition is also established for more general scoring schemes allowing general letter-to-letter alignment penalties and block deletion penalties. We give a general method for applying the bounded increments martingale method to Lipschitz functionals of Markov processes. The phase transition holds for matching Markov chains and for nonoverlapping repeats in a single sequence.