Hi greengaroo,
The algorithm is this:-
Pictorial representation:-
http://picpaste.com/triplets-IQMFT1QY.jpg
`Triplets :: S=('b,c|a', 'a,c|d', 'd,e|b'),
Species :: L={a,b,c,d,e}
TreeConstruct(S):
1.] Let L be the set of species in S. Build G(L) the auxillary graph.
2.] Let C1,C2....Cq be the set of connected components in G(L).
3.] If q>1,then
- For i=1,2.....q, let S(i) be the set of triplets in S labeled by
+the set of leaves in C(i).
- Let T(i) = TreeConstruct(S(i))
- Let T be a tree formed by connecting all T(i) with the same paren
+t node. Return T.
4.]If q=1 & C1 contains exactly one leaf,return the leaf ,else return
+fail.
`
I have updated the code and now it takes input connections in form of triplets and prints the connected components of the graph.
`use strict;
use warnings;
use Graph;
@ARGV = ('b,c|a', 'a,c|d', 'd,e|b') unless @ARGV;
my %HoA;
foreach ( @ARGV ) {
m/^([a-z])[,]([a-z])[|]([a-z])$/ ;
push @{$HoA{$1}}, $2;
}
print "\n===========\@HoA=====\n";
print "from->to\n";
while (my ($key, $values) = each %HoA) {
print $key, "=> [", join(',', @$values), "]\n";
}
my $g = Graph->new( undirected => 1 );
for my $src ( keys %HoA ) {
for my $tgt ( @{ $HoA{$src} } ) {
$g->add_edge($src, $tgt);
}
}
my @subgraphs = $g->connected_components;
my @allgraphs;
for my $subgraph ( @subgraphs ) {
push @allgraphs, {};
for my $node ( @$subgraph ) {
if ( exists $HoA{ $node } ) {
$allgraphs[-1]{$node} = [ @{ $HoA{$node} } ];
}
}
}
print "----connected components------------";
use YAML; print Dump \@allgraphs;
-------------OUTPUT----------------
===========@HoA=====
from->to
a=> [c]
b=> [c]
d=> [e]
----connected components---------------
- a:
- c
b:
- c
- d:
- e
`
Hope this helps you get an idea |
Comment onRe: phylogenetic tree construction using perl