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

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

内联中: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(文档):

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对象,而不是循环遍历各个数据元素.

Answer 2

那些看起来像基因序列.如果字符串都是8个字符,并且可能代码的域是(A,C,G,T),您可以考虑在处理之前以某种方式转换数据.那将只给你65536个可能的字符串,所以你可以专门实现你的实现.

例如,您编写一个采用8个字符的字符串并将其映射为整数的方法. 记住这一点,以便操作快速.接下来,编写一个比较函数,给定两个整数,告诉你它们是如何不同的.您可以unless ( $a != $b )在调用比较之前使用数字相等性测试在合适的循环结构中调用它 - 如果您愿意,可以使用相同代码的短路.