Finden von Base Overlap Counts und internen Lücken in zwei Strängen

Question

Ich habe diese zwei Strings von gleicher Länge, die ich vergleichen muss. Ich möchte Überlappungsbasis (.) Und interne Lücke (*) finden. Nachfolgend finden Sie das Beispiel:

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

Anzahl der Überlappung = 33. Anzahl interner gap = 2.

ich kein Problem haben, die Anzahl der Überlappung zu finden. Aber ich habe das Problem, interne Lücke zu finden. Unten ist der aktuelle Code, den ich habe. Es ist schrecklich langsam. Im Prinzip muss ich Millionen solcher Paare berechnen.

#!/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"; 

Bitte beraten wie ich interne Lücke und Überlappung effizient finden kann.

Answer 1

Sie können ein bitweises OR für die Strings verwenden, um die Bereiche in einer Zeichenfolge zu finden, die in der anderen Zeichenfolge mit leeren Bereichen überlappen. Dieses Verfahren hat auch den Effekt, dass die Überlappung enthüllt durch niedrigeren Fall nicht überlappende Zeichen umwandelt, wodurch die Überlappung ganz einfach zu finden:

#!/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; 

Drucke:

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

Weitere Informationen zu Zeichenfolge bitweise Operationen:

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

Answer 2

die Lücken Unter der Annahme, nie überlappen, können Sie diese mit regulären expre lösen sionen. Hier ist eine Antwort für Ihre s1.

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