perl - 查找相同长度的两个字符串之间不匹配位置的最快方法

Question

我有数百万对相同长度的字符串，我想比较和查找它们不匹配的位置。

例如，对于每个 $str1 和 $str2，我们希望找到不匹配的情况$str_source 的位置:

$str_source = "ATTCCGGG";

$str1       = "ATTGCGGG"; # 1 mismatch with Str1 at position 3 (0-based)
$str2       = "ATACCGGC"; # 2 mismatches with source at position  2 and 7

有没有快速的方法。目前我有循环的 C 风格方法使用“substr”函数计算两个字符串中的每个位置。但这种方法非常慢。

my @mism_pos;
for $i (0 .. length($str_source)) {
   $source_base = substr($str_source,$i,1);
   $str_base    = substr($str2,$i,$1);

  if ($source_base ne $str_base) {
     push @mism_pos,$i;
  }

}

Answer 1

Inline::C

计算很简单，用Inline::C来做。(阅读 perldoc Inline::C-Cookbook 和 perldoc Inline::C 以获取文档):

use Inline C => << '...';                                                       
  void find_diffs(char* x, char* y) {                                           
    int i;                                                                      
    Inline_Stack_Vars;                                                          
    Inline_Stack_Reset;                                                         
    for(i=0; x[i] && y[i]; ++i) {                                               
      if(x[i] != y[i]) {                                                        
        Inline_Stack_Push(sv_2mortal(newSViv(i)));                              
      }                                                                         
    }                                                                           
    Inline_Stack_Done;                                                          
  }                                                                             
...                                                                             

@diffs= find_diffs("ATTCCGGG","ATTGCGGG");  print "@diffs\n";                   
@diffs= find_diffs("ATTCCGGG","ATACCGGC");  print "@diffs\n";                   

这是该脚本的输出:

> script.pl 
3
2 7

PDL

如果你想在 Perl 中快速处理大量数据，请学习 PDL (Documentation):

use PDL; 
use PDL::Char;                                                                  
$PDL::SHARE=$PDL::SHARE; # keep stray warning quiet 

my $source=PDL::Char->new("ATTCCGGG");                                          
for my $str ( "ATTGCGGG", "ATACCGGC") {                                         
  my $match =PDL::Char->new($str);                                              
  my @diff=which($match!=$source)->list;                                        
  print "@diff\n";                                                              
}

(与第一个脚本相同的输出。)

注释:我在基因组数据处理中非常愉快地使用了 PDL。结合对存储在磁盘上的数据的内存映射访问，可以快速处理大量数据:所有处理都在高度优化的 C 循环中完成。此外，您还可以通过Inline::C轻松访问相同的数据。对于 PDL 中缺少的任何功能.

但请注意，创建一个 PDL 向量的速度相当慢(时间恒定，对于大型数据结构来说是可以接受的)。因此，您宁愿一次性使用所有输入数据创建一个大型 PDL 对象，而不是循环遍历各个数据元素。