Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: supertree construction in perl

by BrowserUk (Pope)
on Oct 07, 2012 at 20:31 UTC ( #997715=note: print w/ replies, xml ) Need Help??


in reply to supertree construction in perl

You keep asking this question, but until you can describe your problem in English -- rather than dissertationease -- you're unlikely to get a solution.

You have not yet described what "a triple" is or signifies; nor provided links to a viable description of "Alfred Aho's algorithm".

And you keep introducing specialist terms -- induced subgraphs, supertrees -- that will only make sense to speciologists.

To get help with this, you will need to step back from the specialisation and explain the problem in terms that programmers will understand.

(And just to show I'm not being unnecessarily harsh here. After your first post I downloaded and read:

I'm reasonably adept at reading between the BS that these types of papers are couched in, and I did gain some insights into the nature of the problem you are trying to tackle, but in terms of trying to turn the (so-called) algorithm descriptions in those papers into a practical implementation. I'm none the wiser.)


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


Comment on Re: supertree construction in perl
Re^2: supertree construction in perl
by zing (Beadle) on Oct 07, 2012 at 20:49 UTC
    BrowserUK thanks for letting me know the trouble Im causing. So here's it is sir

    http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0772DCA9649E3596FE5319A41B0F3193?doi=10.1.1.135.7740&rep=rep1&type=pdf

    You just need to read the first 4 pages.Its a very quick read (not a lengthy research paper) and the most relevant and elaborate explanation on the algorithm and the terms. Hope it helps

    TRIPLETS(input) and SUPERTREE(output) look like these

    http://ars.sciencedirect.com/content/image/1-s2.0-S0166218X10000983-gr1.jpg

    The picture link above has the exact triplets for my problem and the exact supertree(output) expected

Re^2: supertree construction in perl
by zing (Beadle) on Oct 09, 2012 at 15:14 UTC
    Hi BrowserUk, Did you find any solution to my problem. Please help me on this. I have dealt with all the aspects of the algorithm in isolation but am not able to put it all together(as is required by the algorithm). Help me on this.

      Sorry, but as I said, I find the "algorithm description" in the paper you cited totally incomprehensible. It could be an alchemist's recipe or Archimedes' exclamation when stubbed his toe getting out of the bath for all the sense I can make of it. Constructed to impress rather than convey information. Further, I personally think that (much of) the literature on the subject is wrong, but I haven't reached the point of proof yet.

      I did come across this description of Aho's algorithm which at a cursory glance seems to be infinitely clearer:

      The following procedure is an implementation of the algorithm presented by Aho et al. (1981) with modifications for dealing with incompatibilities.
      1. A subset of the orthologous-repeats table is created, in which only “relevant” rows (organisms) are considered (initially all rows, since all organisms are being considered). Within this subset of rows, only those columns in which at least two rows have a 1 and one row has a 0 are considered.
      2. Using this subset of the original repeat occurrence table, a graph is created by iterating through the columns. If two rows both have a 1 in a given column, an edge of weight 1 is created between the two corresponding organisms. If an edge already exists between those two organisms, its weight is incremented by 1.
      3. Multiple connected components are sought within the graph. If the graph contains a single connected component, weak edges must be eliminated. This is accomplished by removing edges, beginning with those of weight 1 and incrementally removing edges of greater weight, until multiple connected components arise.
      4. Steps 1-3 are recursively applied to each connected component containing more than two organisms. The “relevant” rows in each run are the organisms within the connected component.

      Consider the above example illustrated in Table 3B. The phylogenetic inference of column i is supported by column h, and column k is supported by column l. Thus, in the shared-repeat graph, edges (A, B) and (C, D) have weight 2, while the edge (A, C) has weight 1. Removing the minimum weight edge is akin to removing column j, which has the least support.

      I haven't pursued it because I'd rather finish or abandon my own experiments before I get familiar with someone else's method; but maybe it will help you to bring your code together. Good luck.


      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

        BrowserUK here is the original paper by Alfred Aho(1981, SIAM journal of computing) on which my research is based. The paper is more approachable by computer scientists unlike the recent ones that I posted in here. http://www.smallfiles.org/download/2927/Aho_et_al_paper.pdf.html

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://997715]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2014-10-22 08:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (114 votes), past polls