8

メイン文字列でn個の不一致を許容する文字列で可能な限り長い部分文字列を見つけるための効率的な解決策を探しています

例: 主弦

  1. AGACGTAC TACTCTACT AGATGCA*TACTCTAC*
  2. AGACGTAC TACTCTACT AGATGCA*TACTCTAC*
  3. AGACGTAC TACTCTACA AGATGCA*TACTCTAC*
  4. AGACGTAC TACTTTACA AGATGCA*TACTCTAC*

検索文字列：

  1. TACTCTACT : これは、上記のメイン文字列のすべてに一致すると見なされます。

また、部分文字列の一部がメイン文字列の最後にある場合もあり、それも取り上げたいと思います。

何点かご教示いただければ幸いです。

PS: 1 つの検索文字列と、部分文字列を検索するための約 1 億のメイン文字列があります。

ありがとう！-アビ

4

2 に答える 2

11

これがあなたの求めているものかどうかはわかりませんが、BioPerl には次のような近似 grep ツールがありますBio::Grep::Backend::Agrep。

Bio::Grep::Backend::Agrep は agrep でクエリを検索します

そしてagrep「おおよそのgrep」です。私の知る限り、これはデータベースを構築し、そのデータベースを使用して検索を高速化するため、これが目的のように聞こえます。

DNA シーケンスを扱っているように見えるので、おそらく BioPerl は既にインストールされています。

直接使用することもできますString::Approx：

近似一致 (あいまい一致) の Perl 拡張機能

ただし、それBio::Grep::Backend::Agrepはより高速で、あなたのタスクにより適していると思います。

于 2011-06-06T23:27:52.953 に答える
3 
use strict;
use warnings;
use feature qw( say );

sub match {
   my ($s, $t, $max_x) = @_;

   my $m = my @s = unpack('(a)*', $s);
   my $n = my @t = unpack('(a)*', $t);

   my @length_at_k     = ( 0 ) x ($m+$n);
   my @mismatches_at_k = ( 0 ) x ($m+$n);
   my $offset = $m;

   my $best_length = 0;
   my @solutions;
   for my $i (0..$m-1) {
      --$offset;

      for my $j (0..$n-1) {
         my $k = $j + $offset;

         if ($s[$i] eq $t[$j]) {
            ++$length_at_k[$k];
         }
         elsif ($length_at_k[$k] > 0 && $mismatches_at_k[$k] < $max_x) {
            ++$length_at_k[$k];
            ++$mismatches_at_k[$k];
         }
         else {
            $length_at_k[$k] = 0;
            $mismatches_at_k[$k] = 0;
         }

         my $length = $length_at_k[$k] + $max_x - $mismatches_at_k[$k];
         $length = $i+1 if $length > $i+1;

         if ($length >= $best_length) {
            if ($length > $best_length) {
               $best_length = $length;
               @solutions = ();
            }

            push @solutions, $i-$length+1;
         }
      }
   }

   return map { substr($s, $_, $best_length) } @solutions;
}

say for match('AABBCC', 'DDBBEE', 2);

出力：

AABB
ABBC
BBCC
于 2011-06-07T06:24:24.963 に答える