Sept. 9, 2015, 3:45 a.m. by Rosalind Team
When the position of the root in an evolutionary tree is unknown, we can simply assign the root to any edge that we like, apply SmallParsimony from “Implement SmallParsimony” to the resulting rooted tree, and then remove the root. It can be shown that this method provides a solution to the following problem.
Find the most parsimonious labeling of the internal nodes in an unrooted tree.
Given: An unrooted binary tree with each leaf labeled by a string of length m.
Return: A labeling of all other nodes of the tree by strings of length m that minimizes the parsimony score of the tree.
Note on formatting: Your internal node labelings may differ from the sample provided.
4 TCGGCCAA->4 4->TCGGCCAA CCTGGCTG->4 4->CCTGGCTG CACAGGAT->5 5->CACAGGAT TGAGTACC->5 5->TGAGTACC 4->5 5->4
17 TCGGCCAA->CCAGGCAC:4 CCTGGCTG->CCAGGCAC:3 TGAGTACC->CAAGGAAC:4 CCAGGCAC->CCTGGCTG:3 CCAGGCAC->CAAGGAAC:2 CCAGGCAC->TCGGCCAA:4 CACAGGAT->CAAGGAAC:4 CAAGGAAC->CACAGGAT:4 CAAGGAAC->TGAGTACC:4 CAAGGAAC->CCAGGCAC:2
