Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

phylogenetic tree construction using perl

by zing (Beadle)
on Sep 25, 2012 at 16:00 UTC ( [id://995583]=perlquestion: print w/replies, xml ) Need Help??

zing has asked for the wisdom of the Perl Monks concerning the following question:

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"; } -----------OUTPUT---------- [hzing@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

Replies are listed 'Best First'.
Re: phylogenetic tree construction using perl
by BrowserUk (Patriarch) on Sep 25, 2012 at 17:09 UTC

    Do you have a second (more extensive) example for testing?


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    RIP Neil Armstrong

Re: phylogenetic tree construction using perl
by pvaldes (Chaplain) on Sep 27, 2012 at 18:44 UTC

    Trying to reinvent the wheel?

    take a look to bioperl

    You'll be delighted when you see

    that can build a Bio::Tree

    (feeling like Edgar Allan Poet, today)

      It has come to my mind
      that the best way to learn
      is doing things by yourself
        the osmosis and the telepathy are not the ways humans learn
Re: phylogenetic tree construction using perl
by greengaroo (Hermit) on Sep 26, 2012 at 19:36 UTC

    I don't know much about this, but have you tried this suite of modules to help you: Bio-Phylo? There are some Tree building modules in there.

    There are no stupid questions, but there are a lot of inquisitive idiots.
      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

        I'm still reading through the Triplet Methods paper, so I'm certain my understanding is not only limited but wrong. Nonetheless, section 7.4.1 ("Reconstruct a network by a sorting network") caught my eye for the simple reason that Algorithm-Networksort exists on CPAN and I am its author.

        So if the module can be of use to you, great. If there's a feature that you need from it that's doable, I'd be more than happy to add it to the module. Let me know.

        By the way, your link to your jpeg on picpaste doesn't display anything.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://995583]
Front-paged by BrowserUk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2024-03-19 02:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found