Tool for computing all solutions to the small parsimony problem
0
0
Entering edit mode
17 months ago

While there are tools such as PHYLIP and Bio++ for solving the small parsimony problem: finding a parsimonious assignment of states of qualitative characters to the internal nodes of a phylogenetic tree, given states of such characters at the leaves of a tree and a cost matrix which dictates the cost of transitioning from one state to another in the tree, is there a tool which computes and outputs _all_ such parsimonious assignments?

This would essentially involve Sankoff's dynamic programming algorithm, building the structure in the upward phase, e.g., as seen in Figure 2 of https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2677398/ , but then in the downward phase, instead of finding one spanning tree, it outputs _all_ spanning trees: the resulting parsimonious assignments

snp • 370 views
ADD COMMENT
0
Entering edit mode

There can be (often are) exponentially many solutions. Why would want to enumerate them all?

ADD REPLY

Login before adding your answer.

Traffic: 2789 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6