Sept. 9, 2015, 3:45 a.m. by Rosalind Team
The pseudocode for SmallParsimony is shown below. It returns the parsimony score for a binary rooted tree T whose leaves are labeled by symbols stored in an array Character (i.e., Character(v) is the label of leaf v). At each iteration, it selects a node v and computes sk(v) for each symbol k in the alphabet. For each node v, SmallParsimony maintains a value Tag(v), which indicates whether the node has been processed (i.e., Tag(v) = 1 if the array sk(v) has been computed and Tag(v) = 0 otherwise). We call an internal node of T ripe if its tag is 0 but its children’s tags are both 1. SmallParsimony works upward from the leaves, finding a ripe node v at which to compute sk(v) at each step.
Find the most parsimonious labeling of the internal nodes of a rooted tree.
Given: An integer n followed by an adjacency list for a rooted binary tree with n leaves labeled by DNA strings.
Return: The minimum parsimony score of this tree, followed by the adjacency list of the tree corresponding to labeling internal nodes by DNA strings in order to minimize the parsimony score of the tree.
Note: Remember to run SmallParsimony on each individual index of the strings at the leaves of the tree.
4 4->CAAATCCC 4->ATTGCGAC 5->CTGCGCTG 5->ATGGACGA 6->4 6->5
16 ATTGCGAC->ATAGCCAC:2 ATAGACAA->ATAGCCAC:2 ATAGACAA->ATGGACTA:2 ATGGACGA->ATGGACTA:1 CTGCGCTG->ATGGACTA:4 ATGGACTA->CTGCGCTG:4 ATGGACTA->ATGGACGA:1 ATGGACTA->ATAGACAA:2 ATAGCCAC->CAAATCCC:5 ATAGCCAC->ATTGCGAC:2 ATAGCCAC->ATAGACAA:2 CAAATCCC->ATAGCCAC:5
