Phylogenetic tree construction using perl

Dev Shed Forums Sponsor:

September 25th, 2012, 11:28 AM

rushadrena

Registered User

Join Date: Sep 2011

Posts: 18

Time spent in forums: 5 h 18 m 40 sec
Reputation Power: 0

Phylogenetic tree construction using perl

Hi all, Im a bioinformatician at a research centre.So I am trying to build a supertree using the algorithm "TreeConstruct" described in section 7.2.3 of this article - http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0772DCA9649E3596FE5319A41B0F3193?doi=10.1.1.135.7740&rep=rep1&type=pdf

I have managed to write a code to read the triplets and display the connections (ignoring redundancy)

use strict;
use warnings;

@ARGV = ('a,b|c', 'c,d|e', 'a,d|e') 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";
}

#[vanilla@localhost perl]$ perl input.pl

#===========@HoA=====
#from->to
#c=> [d]
#a=> [b,d]

But Im not able to proceed beyond this point. Especially the second and third step of the algorithm are very difficult for me to implement. Please help

September 25th, 2012, 07:44 PM

Laurent_R

Contributing User

Join Date: Jun 2012

Posts: 514

Time spent in forums: 4 Days 20 h 37 m 3 sec
Reputation Power: 405

Hum, this is a cross post with perl Guru.

Quote:

Originally Posted by rushadrena

Hi all, Im a bioinformatician at a research centre.

You are a bioinformatician at a research centre? Gee, don't take is as an offense, but the last post on which I tried to help you (on the Perl Guru forum, I think) led me to think that you are rather an absolute complete beginner in the art of programming and debugging, irrespective of the programming language being used.

Again, don't take it as an offense, I am not even a beginner in biology.

As for your problem, I am sorry, but I am in a trip right now and I have no time now for reading the article you point to, and won't have any time to do it before at best next week-end.

September 26th, 2012, 04:54 PM

rushadrena

Registered User

Join Date: Sep 2011

Posts: 18

Time spent in forums: 5 h 18 m 40 sec
Reputation Power: 0

None taken Laurent. BTW The algorithm is this:- Pictorial representation:- http://picpaste.com/triplets-IQMFT1QY.jpg

PHP Code:


		
			
 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 parent 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.

Code:

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

Phylogenetic tree construction using perl

Developer Shed Advertisers and Affiliates