2つの文字列でのベースオーバーラップ数と内部ギャップの検出

Question

私はこれと同じ長さの2つの文字列を比較する必要があります。 オーバーラップベース（。）と内部ギャップ（*）を探したい。オーバーラップの

------ACTAAAAATACAAAAA--TTAGCCAGGCGTGGTGGCAC 
-----TACTAAAAATACAAAAAAATTAGCCAGGTGTGGTGG--- 
     ................**................. 

数= Iがオーバーラップの数を求める問題はない内部ギャップ= 2

の33 数：以下の例です。しかし、私は問題 内部のギャップを見つけることがあります。以下は私の現在のコードです。それはひどく遅いです。 原則として、私はそのようなペアの何百万もを計算する必要があります。

#!/usr/bin/perl -w 
my $s1 = "------ACTAAAAATACAAAAA--TTAGCCAGGCGTGGTGGCAC"; 
my $s2 = "-----TACTAAAAATACAAAAAAATTAGCCAGGTGTGGTGG---"; 

print "$s1\n"; 
print "$s2\n"; 


my %base = ("A" => 1, "T" => 1, "C" => 1, "G" => 1); 

my $ovlp_basecount = 0; 
my $internal_gap = 0; 

foreach my $si (0 .. length($s1) ) { 


    my $base1 = substr($s1,$si,1); 
    my $base2 = substr($s2,$si,1); 


    # Overlap 
    if ($base{$base1} && $base{$base2}) { 
     $ovlp_basecount++; 
    } 

    # Not sure how to compute internal gap 

} 


print "TOTAL OVERLAP BASE = $ovlp_basecount\n"; 
print "TOTAL Internal Gap \?\n"; 

内部ギャップとオーバーラップを効率的に見つける方法を教えてください。

Answer 1

文字列のビット単位のORを使用して、ある文字列内の空白領域と重複する領域を見つけることができます。

#!/usr/bin/perl 

use strict; 
use warnings; 

my $s1 = "------ACTAAAAATACAAAAA--TTAGCCAGGCGTGGTGGCAC"; 
my $s2 = "-----TACTAAAAATACAAAAAAATTAGCCAGGTGTGGTGG---"; 

$s1 =~ tr/-/\x20/; 
$s2 =~ tr/-/\x20/; 
my $or = $s1 | $s2; 
(my $gap) = $or =~ m/^.*[ACTG]([actg]+)[ACTG].*$/; 
(my $overlap = $or) =~ s/[^A-Z]//g; 

print "s1:  '$s1'\n"; 
print "s2:  '$s2'\n"; 
print "OR:  '$or'\n"; 
printf "Gap:  '%s' (%d)\n", $gap,  length $gap; 
printf "Overlap '%s' (%d)\n", $overlap, length $overlap; 

プリント：

s1:  '  ACTAAAAATACAAAAA TTAGCCAGGCGTGGTGGCAC' 
s2:  '  TACTAAAAATACAAAAAAATTAGCCAGGTGTGGTGG ' 
OR:  '  tACTAAAAATACAAAAAaaTTAGCCAGGWGTGGTGGcac' 
Gap:  'aa' (2) 
Overlap 'ACTAAAAATACAAAAATTAGCCAGGWGTGGTGG' (33) 

を文字列の詳細については、このプロセスは、あまりにも非常に単純なオーバーラップを見つける従って、下部ケースに非重複文字を変換することによってオーバーラップを明らかにする効果を有しますビット単位演算：ギャップが重なることはありません、あなたはこの使用して定期的にexpreを解決することができると仮定すると、

http://teaching.idallen.com/cst8214/08w/notes/bit_operations.txt

Answer 2

シオンズ。 s1の回答は次のとおりです。

echo '------ACTAAAAATACAAAAA--TTAGCCAGGCGTGGTGGCAC' | perl -ne '$s = 0; foreach(/[GTAC](-+)[GTAC]/) { $s += length($1); } print "$s\n";' 
2