in reply to Complicated pattern match

You may want to have a look at Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, although I haven't got a copy on my desk right now, I'm pretty sure some nice algorithm for this problem is given. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison might also be worth a try.

Nevertheless I had a go at it, the code is shown below.

Just my 2 cents, -gjb-

use strict;
use warnings;

$a = 'ATGGAGTCGACGAATTTGAAGAAT';
$b = 'xxxxxxATGGAGyxxxTCGAzxxxxCGAATTTGAAxxwGAAT';

my $prevPos = 0;
my $reA = createRegex($a);
while ($b =~ /$reA/g) {
    my $match = $&;
    my $skipped = substr($`, $prevPos);
    print "[$skipped]\n";
    $a = substr($a, length($match));
    last if length($a) == 0;
    $prevPos = pos($b);
    $reA = createRegex($a);
}

sub createRegex {
    my ($str) = @_;
    my @chars = split(//, $str);
    my $firstChar = shift(@chars);
    my $re = '';
    foreach my $char (reverse @chars) {
        $re = '(?:' . $char . $re . ')?';
    }
    return $firstChar . $re;
}

[download]

In Section Seekers of Perl Wisdom