Reconstructing evolutionary graphs: 3D parsimony

The increasing recognition that symbioses have greatly altered evolution through genome fusions is creating a need for algorithms that can reliably detect and reconstruct fusions. Here, we generalize the bootstrappers gambit algorithm (a quartet method) in order to permit it to analyze both bifurcations and fusions under a single mathematical model, and thereby detect past genomic branchings and endosymbioses. This new method, 3-dimensional parsimony, can be applied to aligned sequences, such as gene, indel, or other genomic presence/absence sequences. It also provides a statistical measure of support for each possible graph. The usefulness of this method is demonstrated by applying it to the ring of life.