1

複数のシーケンスで最長共通部分文字列 (LCS) を見つけようとしています。

CPAN には、次のような 2 つのシーケンスの LCS アルゴリズムを実装するモジュールが多数あります。Algorithm::差分と String::LCSS_XSですが、複数のシーケンスにわたる LCS は必ずしもそれらの 2 つの間の LCS であるとは限らないため、2 つ以上のシーケンスで動作するようにそれらを拡張するのに苦労しています。

その名前に反して、Algorith::MLCSは実際には LCS を返すのではなく、多数の配列のすべての共通要素 (これも非連続) を返すことに注意してください。設計上壊れているという印象ですが、間違っているかもしれません。

Algorithm::DiffとAlgorith::MLCSは、最長共通部分文字列の問題ではなく、最長共通部分列の問題を解決します。

n=2 アルゴリズムを拡張する明白な方法はありますか、それとも自分のバージョンを実装する必要がありますか? はいの場合、どのように？

ありがとう。

4

1 に答える 1

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;
于 2013-12-14T20:35:33.370 に答える