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 亿个主字符串来搜索子字符串。

谢谢！-阿比

4

2 回答 2

11

我不确定这是你所追求的，但 BioPerl 有一个名为的近似 grep 工具Bio::Grep::Backend::Agrep：

Bio::Grep::Backend::Agrep 使用 agrep 搜索查询

并且agrep是“近似grep”。AFAIK，这会建立一个数据库，然后使用该数据库来加快您的搜索速度，所以这听起来像是您所追求的。

看起来您正在处理 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 回答