두 개의 문자열에서 기본 겹침 및 내부 갭 찾기

Question

나는이 두 개의 동일한 길이의 문자열을 비교해야합니다. 오버랩베이스 (.)와 내부 갭 (*)을 찾고 싶습니다. 중복

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

번호 = 내가 중복의 수를 찾는 아무런 문제가 없을 내부 격차 = 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) 

을 문자열에 대한 자세한 내용은이 프로세스는 너무 매우 간단 중복을 찾는 따라서, 낮은 경우에 중복되지 않는 문자를 변환함으로써 중복을 공개하는 효과가 있습니다 비트 연산 : 중복 결코 격차를 가정

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

Answer 2

, 당신이 사용하는 일반 expre를 해결할 수 있습니다 다. s1에 대한 답변입니다.

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