ai-msa:用于 DNA 匹配的多序列比对

多序列比对 尽可能接近地映射不同的字符串。 一项主要应用是 DNA 匹配 描述 词汇表 V 中有 K 个字符串 Xi。每个字符串 Xi 的长度为 Ni。 目标是将字符串相互映射。 转换是一个函数 F，它接受一个字符串并返回另一个字符串。 所有 F(Xi) 具有相同的长度 N。N 大于等于所有 Ni。 函数 F 只允许对原始字符串进行一次更改——它可以引入破折号。 它可以在任何位置引入任意数量的破折号。 X 到 F(X) 的转换成本是 CC*破折号数，CC 是一个常数。 一旦所有字符串都被转换，匹配步骤只匹配每个位置的字符。 两个字符之间的匹配成本由对称函数 MC(c1, c2) 给出，其中 c1 和 c2 是两个字符 ε VU {-}。 两个字符串的匹配成本是它们在每个位置的转化匹配成本之和。 最后，K 个字符串的匹配成本是每对之间成对匹配成本的总和。