Re^2: recursive algorithm

[remiah]

If your structure, "((...)..(((....)).))" means tree structure like s-expression in lisp, and "." matches any gene, "GAGGGUCCUUUCAGUAGCAC" could match 11 trees.

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

my $basestring = 'GAGGGUCCUUUCAGUAGCAC';
my @bases=split(//,$basestring);
my $parenstring = '((...)..(((....)).))';
my $gene_cnt = $parenstring =~ tr/\.//;
my $g_idx;
print "str=$basestring, gene_cnt=$gene_cnt\n";
for (my $idx = 0 ; $idx <= (length($basestring)- $gene_cnt);  $idx++){
    $g_idx=$idx;
    print Dumper parse($parenstring);
}

sub parse{
    my $str=shift;
    my $tree=[];

    while($str =~ s{ \A  #top of string
                     \s* #one space or not
                        (
                            [\(] | [^\s\(]+ #'(' or token(.)
                        )
                    }{}x) {
        my $token;
        if( $1 eq '(' ){
            my $nest=1;
            my $pos;
            for($pos=0; $pos<length($str); $pos++){ #till target ')'
                my $c=substr($str, $pos, 1);
                $nest +=
                    $c eq '(' ?  1
                              : $c eq ')' ? -1
                              : 0;
                last unless $nest;
            }
            my $paren=substr($str, 0, $pos + 1, ''); #erase
            substr($paren, -1, 1, '');
            $token=parse($paren);
        } else { #here $1 is '.'
            $token=$1;
            $token =~ s/\./$bases[$g_idx++]/g;
        }
        push @$tree, $token;
    }
    return($tree);
}

I don't know what is "hydrogen bonds", no knowledge for genes. I hope you to describe what you are going to do, and get help of monks.

sub parse() is a little modified one from kogai dan's example(written in japanese).

regards