Расширение строки с помощью рекурсии в Perl

Question

Учитывая начальную строку, я хотел бы расширить ее, используя хэш префикса и список чтения, Я хочу расширить эту строку следующим образом:

1. Входная начальная строка $seed
2. Извлеките последнюю k основу этого семени
3. Проверьте prefix_hash для чтения в read_list (читает где первая k-база) то же самое с семенем.
4. Слияние, которое читает до конца $ seed
5. Повторите шаг 2 для объединенных операций чтения, пока не будет продлен конец

Я застрял с моим кодом ниже:

use strict;
use Data::Dumper;
use Carp;

my $k = 2;

my %readlist = (

    "read1" => "ACTGA",
    "read2" => "ACAAA",
    "read3" => "CTCGC",
    "read4" => "GAGGG",
    "read5" => "TTTCC",
);


my %prefix_hash = (

    # This is a hash of array (prefix hash). 
    # The key is the last base
    # And array is the read that contain that base
    # at first k position
    # in this case k = 2

    "AC" => ["read1","read2"],
    "AG" => ["read3"],
    "GA" => ["read4"],
    "TT" => ["read5"]

);


my $seed = "AAAAC";


my @newreads = extend_seed($seed);


sub extend_seed {

    my  $str    = shift;

    my @new_str;
    my $first_lastk_str = substr($str,-($k));

    print "$first_lastk_str\n";
    # I'm stuck here how can I recurse and merge


    return @new_str;
}

Учитывая пример выше. Я хочу получить следующий вывод

Intial      AAAAC

First_merge AAAACTGA  # Seed merge with Read 1 
            AAAAACAA  # Seed merge with Read 2

Last_merge  AAAACTGAGGG # First_merge merge with Read 4 

Какой способ это сделать?

Answer 1

Сначала вам нужна подпрограмма merge_strings:

sub merge_strings {
    my ($x, $y, $k) = @_;
    return sprintf '%s%s', $x, substr $y, $k;
}

Подпрограмма предполагает, что совпадают последние $k символов $x и первые $k символов $y.

use strict; use warnings;
use Data::Dumper;

my $k = 2;

my %readlist = (
    "read1" => "ACTGA",
    "read2" => "ACAAA",
    "read3" => "CTCGC",
    "read4" => "GAGGG",
    "read5" => "TTTCC",
);

my %prefix_hash = (
    "AC" => ["read1","read2"],
    "AG" => ["read3"],
    "GA" => ["read4"],
    "TT" => ["read5"]
);

my $seed = "AAAAC";

my @newreads = extend_seed($seed, $k, \%prefix_hash, \%readlist);
print Dumper \@newreads;

sub merge_strings {
    my ($x, $y, $k) = @_;
    return sprintf '%s%s', $x, substr $y, $k;
}

sub extend_seed {
    my ($x, $k, $prefix, $reads) = @_;
    my $key = substr $x, -$k;

    return unless exists $prefix->{$key};

    my @ret = map merge_strings($x, $_, $k),
                  @{$reads}{@{ $prefix->{$key} }};

    push @ret, map extend_seed($_, $k, $prefix, $reads), @ret;
    return @ret;
}

Выход:

$VAR1 = [
          'AAAACTGA',
          'AAAACAAA',
          'AAAACTGAGGG'
        ];