A simple example demonstrating how coevolution can be used to improve ancestral sequence reconstruction. This example includes a coevolving forest with two trees, the tree edges are solid lines, while the coevolutionary edges are dashed wavy arrows; the ancestral states (e.g., the labels at the internal nodes x1 and y1) are smaller, while the known nonancestral states are larger and in italics (for formal definitions, see Supplementary Note 1). (A) The reconstructed ancestral states of two proteins (protein x and protein y); for protein x there are two parsimonious solutions: In one solution, all of the labels of the three internal nodes, t1, t2, t3, are “0”; in the second solution, all of the labels of the three internal nodes are “1.” (B) By taking into consideration the coevolution of protein x with protein y, the “all ‘1’ ” solution is chosen for x, thus resolving the ambiguity in the labels of x by using information about protein y with which it interacts, and which has less ambiguous labels.
