Using large trees is surprisingly difficult

There has been a lot of effort and interest in phylogenetics in getting big trees (1000+ taxa). This should be the most difficult problem in phylogenetics -- after all, finding the best tree is generally (under most optimization criteria) NP-hard. My interest, and therefore that of TreeTapper, is in what happens after you get the big tree: using it for understanding biological processes. This should be relatively simple. After searching an enormous tree space to get the best tree, doing something like estimating ancestral states is easy, just a downpass (postorder traversal) and uppass (preorder traversal) calculating probabilities at each node for just one character. In practice, it seems many of the programs in this area fail with large trees, often due to rounding or underflow errors (inferred from my own experiences, and those of NESCent postdocs or visitors Sam Price, Stephen Smith, and Jeremy Beaulieu). Most computer programs use numbers with finite precision -- a number smaller in magnitude than around 10E-308 can't be stored as a double, for example. That's a really small number, but if it's a likelihood (probability of the data given the tree and model), a probability of 10E-308 is just a -lnL of 706.9, a number that isn't that unusual for our sort of problems. Many calculations can just be done using ln likelihoods rather than untransformed likelihoods, but for some calculations this is more difficult (certainly more difficult to code). R apparently quietly rounds things to zero with small numbers, leading to erroneous results [from reports from others -- I haven't verified this]. My program Brownie, which in the development branch can do discrete character reconstruction, failed on a tree of ~1600 taxa due to underflow errors, so I made a new class for really small or small numbers that basically stores numbers in scientific notation, using a double for the mantissa and an int for the exponent (code available here). Other programs might need similar kludges to work. It seems odd to me, doing programming as a biologist without much formal CS training, that common programming languages don't do this sort of thing automatically (in the same way that needing to manage memory in C++ feels surprising), but it is an issue that may become more frequently encountered by us.

The relevance to TreeTapper is how and whether to record information about how programs perform with large trees. The first question is whether it's meaningful. For a simple program with one function, it's possible that it always fails if trees are over N taxa in size or if likelihoods get below X. But for complex programs like Mesquite, they might fail for some trees for some methods but work for others, so just storing a single number might be misleading. A second issue is that gathering the data might be difficult: for a typical user, deciding whether a program crashed with a tree with N taxa due to the tree size or some other bug will be hard. It also seems unreasonable to expect people to report to TreeTapper every time a program works or fails for them and under what conditions (I wouldn't make the time to do so). On the other hand, it would be helpful to users to know that a certain program just can't work with trees of a certain size and helpful for developers to know which programs need tweaking for large trees. I guess for now I won't have a separate field for this and will just rely on user comments on each program page, but let me know if you have any suggestions.

Viewing missing methods/software, part III: Table views

Repeat of the design goals for viewing missing methods/software: 

1. Allow users to see on a tree (using branch coloring) which questions don't have methods, which methods aren't in software, etc.
2. Allow users to arrange the order in which things are displayed: question->criterion->method, or question->character type 1 -> tree type -> branch length type -> data format -> software
3. Allow users to filter by option (only show methods relating to DNA data, for example)
4. Make it fast, intuitive, etc.

I think a way to address these is to create table views; one has all the available methods ("actualmethods"), one has all the available methods and software ("actualsoftware"), and one could have all the imaginable combinations of all options ("biggie"). That way, all the database logic for combining the primitive tables (method->methodtotreetypetobranchlengthtype->treetype, for example) is taken care of at the view creation step, rather than requiring it all to be created on the fly when a user re-orders options. [Aha: so this is a reason for using MVC]. To draw the tree of methods/software based on user choice, one gets the tree structure by looking in the [actually hypothetical] "biggie" table; combinations (edges on the display tree) present in the "actualsoftware" table are shown in the "+methods +software" color (purple?), combinations not present there but in the "actualmethods" table get the "+methods -software" color (black?), and others get the "-methods -software" color (gray?). The only problem with this is the size of the "biggie" table view: except for built-in relations between general and posed questions and posed questions and relevant combinations of characters (see schema), it's basically a massive cross join. That means that if there are 2 data formats, 6 tree formats, and 7 platforms, the table has 2 x 6 x 7 = 84 rows.  The actual "biggie" table, having info on all the imaginable options (input formats, tree types, character types, criteria, etc.) would currently have 1,361,817,600 (1.3 billion) distinct rows. Instead of creating such a huge table, I will have a view ("generaltoposedtochartype") containing the essential relations between general question, posed question, and character combinations (only 2,480 rows currently) and then just have the program returning possible branches for the tree know that all the other options can essentially be cross joined.

I had a bit of trouble creating the initial "actualmethods" view efficiently; Hilmar Lapp, an IT guru here at NESCent (codes for BioPerl, organizes hackathons, organizes people) edited the query to make it more efficient and eliminate return of duplicate rows (without using "distinct"). Below I've posted the sql statement used to make these views in case it's useful for others (or for me in the future).

-- All actual methods

CREATE VIEW 

actualmethods

(

actualmethods_generalquestion,

actualmethods_posedquestion,

actualmethods_char1,

actualmethods_char2,

actualmethods_char3,

actualmethods_treetype,

actualmethods_branchlengthtype,

actualmethods_criterion,

actualmethods_method

)

AS

SELECT

pq.posedquestion_generalquestion,

pq.posedquestion_id,

  cc.charactercombination_char1, 

cc.charactercombination_char2, 

cc.charactercombination_char3,

mttblt.methodtotreetypetobranchlengthtype_treetype,

mttblt.methodtotreetypetobranchlengthtype_branchlengthtype,

   mc.methodtocriterion_criterion,

mttblt.methodtotreetypetobranchlengthtype_method

FROM

methodtotreetypetobranchlengthtype mttblt,

methodtocriterion mc,

methodtocharactercombination mcc,

methodtoposedquestion mpq,

posedquestion pq,

charactercombination cc,

posedquestiontocharactercombination pqcc

WHERE

methodtocriterion_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_charactercombination=charactercombination_id

AND  

methodtoposedquestion_method=methodtotreetypetobranchlengthtype_method

AND

methodtoposedquestion_posedquestion=posedquestion_id

AND

posedquestiontocharactercombination_posedquestion=posedquestion_id

AND  

posedquestiontocharactercombination_charactercombination=charactercombination_id

;

-- all actual methods and software

CREATE VIEW 

actualsoftware

(

actualsoftware_generalquestion,

actualsoftware_posedquestion,

actualsoftware_char1,

actualsoftware_char2,

actualsoftware_char3,

actualsoftware_treetype,

actualsoftware_branchlengthtype,

actualsoftware_criterion,

actualsoftware_method,

actualsoftware_dataformat,

actualsoftware_treeformat,

actualsoftware_applicationkind,

actualsoftware_platform,

actualsoftware_program

)

AS

SELECT

pq.posedquestion_generalquestion,

pq.posedquestion_id,

cc.charactercombination_char1, 

cc.charactercombination_char2, 

cc.charactercombination_char3,

mttblt.methodtotreetypetobranchlengthtype_treetype,

mttblt.methodtotreetypetobranchlengthtype_branchlengthtype,

mc.methodtocriterion_criterion,

mttblt.methodtotreetypetobranchlengthtype_method,

pdf.programtodataformat_dataformat, 

ptf.programtotreeformat_treeformat, 

ppak.programtoplatformappkind_applicationkind, 

ppak.programtoplatformappkind_platform, 

  pmcc.programtomethodtocharactercombination_program

FROM

methodtotreetypetobranchlengthtype mttblt,

methodtocriterion mc,

methodtocharactercombination mcc,

methodtoposedquestion mpq,

posedquestion pq,

charactercombination cc,

posedquestiontocharactercombination pqcc,

programtodataformat pdf,

programtotreeformat ptf,

programtomethodtocharactercombination pmcc,

programtoplatformappkind ppak

WHERE

methodtocriterion_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_method=methodtotreetypetobranchlengthtype_method

AND  

methodtocharactercombination_charactercombination=charactercombination_id

AND  

methodtoposedquestion_method=methodtotreetypetobranchlengthtype_method

AND 

methodtoposedquestion_posedquestion=posedquestion_id

AND 

posedquestiontocharactercombination_posedquestion=posedquestion_id

AND  

posedquestiontocharactercombination_charactercombination=charactercombination_id

AND 

programtomethodtocharactercombination_methodtocharactercombination=methodtocharactercombination_id

AND 

programtomethodtocharactercombination_program=programtodataformat_program

AND 

programtodataformat_program=programtotreeformat_program

AND 

programtotreeformat_program=programtoplatformappkind_program

;

-- all general+posedquestions+chartypes

CREATE VIEW

generaltoposedtochartype

(

generaltoposedtochartype_generalquestion,

generaltoposedtochartype_posedquestion,

generaltoposedtochartype_char1,

generaltoposedtochartype_char2,

generaltoposedtochartype_char3

)

AS

SELECT

generalquestion_id,

posedquestion_id, 

charactercombination.charactercombination_char1, 

charactercombination.charactercombination_char2, 

charactercombination.charactercombination_char3

FROM

charactercombination,

posedquestiontocharactercombination,

posedquestion,

generalquestion

WHERE

posedquestion_generalquestion=generalquestion_id

AND

posedquestiontocharactercombination_charactercombination=charactercombination_id

AND

posedquestiontocharactercombination_posedquestion=posedquestion_id

;

-- all conceivable combinations of parameters other than question and chartype (a massive cross join, probably not used)

CREATE VIEW

crossjoinoptions

(

crossjoinoptions_treetype,

crossjoinoptions_branchlengthtype,

crossjoinoptions_criterion,

crossjoinoptions_dataformat,

crossjoinoptions_treeformat,

crossjoinoptions_applicationkind,

crossjoinoptions_platform

)

AS

SELECT 

treetype_id, 

branchlengthtype_id, 

criterion_id,

dataformat_id,

treeformat_id,

applicationkind_id,

platform_id

FROM

treetype,

branchlengthtype,

criterion,

dataformat,

treeformat,

applicationkind,

platform

;

Updated schema

I've updated the schema slightly, keeping tracks of citations in different tables rather than just keeping one citation field in the reference table. This way, the number of citations over time can be stored (so the rate of increase of citations can be recovered, as well as the number at any point in time). For right now, "citations" will be the number of hits in Yahoo for the title, year, and lead author last name of a reference, since ISI and CrossRef both require payment to use for citation info and Google Scholar's terms of use prohibit display of info from that site (see Rod Page's post about this).

Database schema

Here is the schema for the TreeTapper database. Entries are only shown after being verified by a DB curator (the approved field in each table): this (I hope) will allow users to add missing terms while allowing me to keep the list of terms from getting too disorganized.