Question: Tool for computing all solutions to the small parsimony problem
0
gravatar for murray.patterson
2 days ago by
murray.patterson10 wrote:

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 • 46 views
ADD COMMENTlink written 2 days ago by murray.patterson10

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

ADD REPLYlink written 1 day ago by Rob3.9k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1429 users visited in the last hour