#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    19
    Rep 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
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jun 2012
    Posts
    837
    Rep Power
    496
    Hum, this is a cross post with perl Guru.

    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.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    19
    Rep 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 SBuild G(Lthe 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.....qlet S(ibe 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(iwith the same parent node. Return T.
    4.]If q=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

IMN logo majestic logo threadwatch logo seochat tools logo