string - 序列比对

Question

我有以下关于序列比对的问题：

我们知道，当您想要强制两个序列在​​其整个长度上对齐时，全局对齐算法很有用，而局部对齐会找到两个序列之间相似性最高的一个或多个区域，并从那里向外构建对齐。

当我们有一个非常长的序列和一个小序列文库时，在文库中找到小序列连接的最佳算法是什么，以最小化比对成本？

Answer 1

令 ∑ 为字母表（例如，{A, C, G, T}）。令 L ⊆ ∑* 为短文库序列的集合。计算 L* 的最小状态 DFA (Q, ∑, ∂, q ₀ , F)。

我们一次扫描一个字母的长序列 x ∈ ∑*。令 x' 为已被消费的 x 的前缀。对于每个状态 q ∈ Q，我们维持在 x' 和 y 之间的 Levenshtein 距离的[每个序列 y ∈ ∑* 使得 ∂(q _{0 , y) = q] 上的最小 c q (x')。}

对于空前缀 ε，对于每个状态 q ∈ Q，它认为 c _q (ε) = min {|y|: y ∈ ∑*, ∂(q ₀ , y) = q}，因为 y 和ε 是 y 的长度。在转移图上使用广度优先搜索计算初始表。

给定 x' 和字母 s 的表格，我们计算 c _q (x) 作为 y 的几种可能性的最小值，其中 x = x' s。

1. 字符串 y = y' sz，对齐 s。这种情况下的代价是 min _{q', z: ∂(q', sz) = q} (c _q' (x') + |z|)，可以通过 |Q| 计算 广度优先搜索。

2. 字符串 y = y'，删除 x 中的 s。在这种情况下，成本是 c _q (x') + 1。

3. 字符串 y = y' t 其中 t 是一个字母，用 s 代替 t（反之亦然）。这种情况下的成本是 min _{q', t: ∂(q', t) = q} (c _q' (x') + 1)。

最后，最优对齐成本为 min _{q ∈ F} c _q (x)。对于动态程序，可以以通常的方式重建对齐。

Answer 2

一种天真的方法是尝试每一种排列。如果S是库中每个小序列的排列集，您可以将大序列与 中的每个序列S一一对齐，并查看哪个具有最小对齐成本。不幸的是，这对 CPU 不友好，因为 的大小S将是小序列数量的指数。