跨多個序列的最長公共子串

我試圖找到跨越多個序列的最長公共子串（LCS）。跨多個序列的最長公共子串

有CPAN上一些模塊實現了LCS算法2個序列，如~~Algorithm::Diff和~~String::LCSS_XS，但我有在擴大他們一時間難以有因爲LCS超過2個序列工作跨越多個序列不一定是它們中任何兩個之間的LCS。

值得注意的是，儘管它的名字，Algorith::MLCS實際上並沒有返回LCS，但所有的常見元素（也是非連續的）的一些數組。我的印象是它被設計破壞了，但我可能是錯的。

Algorithm::Diff和Algorith::MLCS解決最長公共子問題，而不是最長的共同子之一。

是否有一種明顯的方式來擴展n = 2的算法，或者我必須實現我的版本？如果是，如何？

謝謝。

2013-12-14 enricoferrero

我不是專家，但我懷疑算法:: MLC的不是「設計打破」。相反，它解決了一個不同的問題。它涉及最長的常見**子序列**問題。如果我理解你的問題，你正在處理最長的常見**子串**問題。我認爲Algorithm :: Diff是相同的：它處理子序列問題。 – FMc

是的，你是正確的，我沒有得到那裏是子字符串和子序列之間的區別！ – enricoferrero

使用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;

來源

2013-12-14 20:35:33 enricoferrero

跨多個序列的最長公共子串

回答

相關問題