将有序事件序列合并到 Table
Merge Ordered Event Sequences into Table
我正在寻找解决以下问题的算法：假设我有一个 collection 有序事件序列，并希望从中创建 table
AB
BC
导致 table 形式
ABC
**
**
第一行是 header。对于每个输入序列，我想要一行在发生的事件的列中带有标记。
另一个更复杂的示例（具有三个序列）是：
AAB
BBA
CBA
导致
CBBAAB
***
***
** *
我知道有时有多种可能的解决方案（例如，两个序列只包含一个事件的简单示例，我可以自由决定哪个先出现）。我只对任何解决方案感兴趣，生成的 header 序列（最后一个示例中的 CBBAAB ）应该尽可能短。
有人知道解决该问题的算法吗？
原来我在这里试图解决的问题叫做（多个）sequence alignment。它在生物信息学中很常见（他们用它来比较 DNA 字符串）。有很多用于比对 DNA 串的工具，但是通用工具的数量似乎相当有限。
noporpoise/seq-align 在 GitHub 上似乎很有前途。我将不得不围绕它构建一些工具来适应我的目的。我的序列元素是多个字符，但由于我没有那么多字符，所以我可以将它们映射到 ASCII 字符。此外，该工具仅进行成对序列比对，因此我将不得不链接调用。为了找到最佳解决方案，我必须对每个可能的链执行它（生成所有排列）。
我相信可以用更简单的方法解决它。对我来说，问题似乎是首先找到最短的公共超序列，然后找到标记 - 用超序列计算每个字符串的公共子序列。
例如：
AAB
BBA
CBA
AAB, BBA 之间的最短公共超序列是 BBAAB 或 AABBA
那么 BBAAB 和 CBA 之间的最短超序列是 CBBAAB 或 AABBA 和 CBA 之间的最短超序列是 CAABBA
现在要查找 AAB 的标记，找到 CBBAAB 和 AAB 之间的公共子序列。
同样适用于 BBA 和 CBBAAB 以及 CBA、CBBAAB
这里有一些链接可以帮助找到它们：
我正在寻找解决以下问题的算法：假设我有一个 collection 有序事件序列，并希望从中创建 table
AB
BC
导致 table 形式
ABC
**
**
第一行是 header。对于每个输入序列，我想要一行在发生的事件的列中带有标记。
另一个更复杂的示例（具有三个序列）是：
AAB
BBA
CBA
导致
CBBAAB
***
***
** *
我知道有时有多种可能的解决方案（例如，两个序列只包含一个事件的简单示例，我可以自由决定哪个先出现）。我只对任何解决方案感兴趣，生成的 header 序列（最后一个示例中的 CBBAAB ）应该尽可能短。
有人知道解决该问题的算法吗？
原来我在这里试图解决的问题叫做（多个）sequence alignment。它在生物信息学中很常见（他们用它来比较 DNA 字符串）。有很多用于比对 DNA 串的工具，但是通用工具的数量似乎相当有限。
noporpoise/seq-align 在 GitHub 上似乎很有前途。我将不得不围绕它构建一些工具来适应我的目的。我的序列元素是多个字符，但由于我没有那么多字符，所以我可以将它们映射到 ASCII 字符。此外，该工具仅进行成对序列比对，因此我将不得不链接调用。为了找到最佳解决方案，我必须对每个可能的链执行它（生成所有排列）。
我相信可以用更简单的方法解决它。对我来说，问题似乎是首先找到最短的公共超序列，然后找到标记 - 用超序列计算每个字符串的公共子序列。
例如：
AAB
BBA
CBA
AAB, BBA 之间的最短公共超序列是 BBAAB 或 AABBA
那么 BBAAB 和 CBA 之间的最短超序列是 CBBAAB 或 AABBA 和 CBA 之间的最短超序列是 CAABBA
现在要查找 AAB 的标记，找到 CBBAAB 和 AAB 之间的公共子序列。
同样适用于 BBA 和 CBBAAB 以及 CBA、CBBAAB
这里有一些链接可以帮助找到它们：