我正在寻找一个有效的解决方案,找到一个字符串中最长的子字符串,容忍主字符串中的n个不匹配
例如:主字符串
搜索字符串:
另外我可能会遇到子串的一部分位于主字符串末尾的情况,我也想选择它。
如果你能给出一些指示,我将不胜感激。
PS:我将有一个搜索字符串和大约1亿个主字符串来搜索子字符串。
谢谢!关于现在
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
我不确定这是你想要的,但BioPerl有一个名为Bio::Grep::Backend::Agrep
的近似grep工具:
Bio :: Grep :: Backend :: Agrep使用agrep搜索查询
而agrep
是“近似grep”。 AFAIK,它构建一个数据库,然后使用该数据库使您的搜索更快,所以这听起来像你所追求的。
看起来你正在使用DNA序列,所以你可能已经安装了BioPerl。
您也可以尝试直接使用String::Approx
:
用于近似匹配的Perl扩展(模糊匹配)
我怀疑Bio::Grep::Backend::Agrep
会更快,更适合你的任务。