Нахождение базовых значений перекрытия и внутреннего разрыва в двух строках

Question

У меня есть две строки одинаковой длины, которые мне нужно сравнить. Я хочу найти основу перекрытия (.) И внутренний зазор (*). Ниже приведен пример:

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

Количество перекрытий = 33. Номер внутреннего зазора = 2.

У меня нет проблем с поиском числа совпадений. Но у меня проблема найти внутренний разрыв. Ниже приведен текущий код, который у меня есть. Это ужасно медленно. В принципе мне нужно вычислить миллионы таких пар.

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

Вы можете использовать побитовое ИЛИ для строк, чтобы найти области в одной строке, которые перекрывают пустые области в другой.Этот процесс также имеет эффект выявления наложения путем преобразования неперекрывающихся символов в нижний регистр, что делает поиск наложения также довольно простым:

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

Предполагая, что пробелы никогда не перекрываются, вы можете решить это с помощью регулярных выражений. Вот ответ для вашего s1.

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