r - 多个(非生物、离散状态)序列的比对

Question

我有一些数据描述一组有序的离散事件(或状态)。有 34 种可能的状态，它们可以按任何顺序发生并且可以重复。每个事件序列可以包含任意数量的事件，并且最重要的是有超过 2 个事件序列。我的最终目标是将这些序列聚类成相似的子集，但我的预感是，除非这些序列对齐，使得等效事件在所有序列中占据相同的位置，否则这没有意义。

我非常熟悉生物序列的多重比对，但我遇到的所有软件(MUSCLE、MAFFT、T-COFFEE、Clustal* 等)都需要 DNA、RNA 或 AA 序列，而我的状态比其中任何一个都多，所以我无法让它们工作。

我已经发现了成对对齐算法的各种实现，例如 R 中的 Needleman-Wunsch，但到目前为止还没有遇到任何 的通用(非生物)实现多种序列比对算法。

例如，假设我的数据如下所示:

1: ABCDEFG
2: ACDGH
3: BDEFEGI
4: AH
5: DEGHI

我的目标是让它看起来像这样:

1: ABCDEF-G--
2: A-CD---GH-
3: -B-DEFE--I
4: A-------H-
5: ---DE--GHI

其中 - 符号表示此序列中不存在事件。这是一个简化的示例，实际上我正在寻找一种可以像生物序列 MSA 算法一样惩罚间隙打开 (-) 的方法。

我发现的唯一可能做到这一点的软件是 Alphamalig ( http://alggen.lsi.upc.es/recerca/align/alphamalig/intro-alphamalig.html )，但它很旧，我无法让它在我的机器上运行。理想情况下，我想要一些可以在 R 中实现的东西。

Answer 1

我建议使用 MAFFT sequence alignment 。通常，这用于对齐生物序列，但它可以选择使用 --anysymbol 来对齐文本。请注意，MAFFT 是一个 bash 脚本，需要输入/输出文件。

输入文件(mafft_anysymbol_input.txt):

>Seq1
ABCDEFG
>Seq2
ACDGH
>Seq3
BDEFEGI
>Seq4
AH
>Seq5
DEGHI

运行 bash 脚本的 R 代码:

#Be sure that input/output and R files share the same path, otherwise you'll have to specify the path in the mafft script call.
x <- 'mafft --anysymbol mafft_anysymbol_input.txt > mafft_anysymbol_output.txt'
system(x)

输出文件的内容(mafft_anysymbol_output.txt):

>Seq1
ABCDEFG--
>Seq2
-ACDGH---
>Seq3
--BDEFEGI
>Seq4
----AH---
>Seq5
---DEGHI-

编辑 - 我现在看到您熟悉生物比对工具。如果您想为文本对齐方式创建自定义评分矩阵，请查看 mafft 选项 --text and --textmatrix 。它需要 ascii 代码输入(额外的数据类型转换)，但您可以选择按分数关联相似的字母(但您选择定义相似)。例如，您可以关联大写和小写字母，或者带有/不带有重音符号的字母。