Assuming (as in my previous post) that the phylogenetic tree is a binary tree, the following code should work.

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

my $sites={'mouse'=>'CGGCGGAAAACTGTCCTCCGTGC',
           'rat'=>  'CGACGGAACATTCTCCTCCGCGC', 
           'human'=>'CGACGGAATATTCCCCTCCGTGC',
           'chimp'=>'CGACGGAAGACTCTCCTCCGTGC'};
my $tree = [['mouse','rat'],['human','chimp']]; 

# Sanity checks
my $len=-1;
treeCheck($tree,$sites,\$len);
              
my @val;
$val[$_]=parsimony(extractLocus($tree,$sites,$_))->[0] for (0..$len-1)
+;
print join('',@val)."\n";


sub treeCheck {
  my ($subTree,$sites,$len)=@_;
  if (ref($subTree) eq 'ARRAY') {
    die "Not a binary tree" if @$subTree != 2;
    treeCheck($subTree->[0],$sites,$len);
    treeCheck($subTree->[1],$sites,$len);
  } else {
    die "Invalid char" if $sites->{$subTree} !~ /^[ATCG]+$/;
    if ($$len<0) {
      $$len=length($sites->{$subTree});
    } else {
      die "Invalid length" if length($sites->{$subTree}) != $$len;
    }
  }
}

sub extractLocus {
  my ($subTree,$sites,$index)=@_;
  if (ref($subTree) eq 'ARRAY') {
    return [extractLocus($subTree->[0],$sites,$index),extractLocus($su
+bTree->[1],$sites,$index)];
  } else {
    my $base=substr($sites->{$subTree},$index,1);
    $base =~ tr/ATCG/1248/;    
    return $base;
  }
}
  
sub parsimony {
  my $locusTree=shift;
  if (ref($locusTree) eq 'ARRAY') {
    my $left=parsimony($locusTree->[0]);
    my $right=parsimony($locusTree->[1]);
    my $count=$left->[0]+$right->[0];
    $count++ if ($left->[1] & $right->[1])==0;
    my $bases=$left->[1] | $right->[1];
    return [$count,$bases]
  } else {
    return[0,$locusTree];
  }
}

[download]

I have significantly changed the input data structures, so $tree is "really" a tree (an AoA..oA) containing the names of the species and $sites is an hash using the species as key. It works with your original data but changing the structure of the tree gives (as to be expected) different results:

With $tree = [['mouse','rat'],['human','chimp']]; 
gives 00100000302011000000100

With $tree = ['mouse',['rat',['human','chimp']]]; 
gives 00100000301011000000100

[download]

Rule One: "Do not act incautiously when confronting a little bald wrinkly smiling man."

In reply to Re: Maximal Parsimony Problem by psini
in thread Maximal Parsimony Problem by neversaint

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.