algorithm - 跨多个序列的最长公共子串

Question

我试图在多个序列中找到最长的公共子串（LCS）。

CPAN 上有许多模块实现了 2 个序列的 LCS 算法，例如算法::Diff和 String::LCSS_XS，但我很难将它们扩展为使用超过 2 个序列，因为跨多个序列的 LCS 不一定是它们中的任何两个之间的 LCS。

值得注意的是，尽管它的名称，Algorith::MLCS实际上并不返回 LCS，而是返回许多数组的所有公共元素（也是非连续的）。我的印象是它被设计破坏了，但我可能错了。

Algorithm::Diff和A​​lgorith::MLCS解决最长公共子序列问题，而不是最长公共子串问题。

有没有明显的方法来扩展 n=2 算法或者我必须实现我的版本？如果是，如何？

谢谢。

Answer 1

使用Tree::Suffix模块可以很容易地解决这个问题。

例子：

#!/usr/bin/env perl
use Modern::Perl;
use Bio::SeqIO;
use Tree::Suffix;

my $seqio = Bio::SeqIO->new(
    -file => "fasta_sequences.txt",
    -format => "Fasta");

my @seqs;

while (my $seqobj = $seqio->next_seq) {
    push @seqs, $seqobj->seq;
}

my $tree = Tree::Suffix->new(@seqs);
my @lcss = $tree->lcs;

say $_ for @lcss;