Evolution of gene neighborhoods within reconciled phylogenies

Abstract

Motivation: Most models of genome evolution integrating gene duplications, losses and chromosomal rearrangements are computationally intract able, even when comparing only two genomes. This prevents large-scale studies that consider different types of genome structural variations.

Results: We define an 'adjacency phylogenetic tree' that describes the evolution of an adjacency, a neighborhood relation between two genes, by speciation, duplication or loss of one or both genes, and rearrangement. We describe an algorithm that, given a species tree and a set of gene trees where the leaves are connected by adjacencies, computes an adjacency forest that minimizes the number of gains and breakages of adjacencies (caused by rearrangements) and runs in polynomial time. We use this algorithm to reconstruct contiguous regions of mammalian and plant ancestral genomes in a few minutes for a dozen species and several thousand genes. We show that this method yields reduced conflict between ancestral adjacencies. We detect duplications involving several genes and compare the different modes of evolution between phyla and among lineages.

Availability: C++ implementation using BIO++ package, available upon request to Sèverine Bérard.

Contact: Severine.Berard@cirad.fr or Eric.Tannier@inria.fr

Supplementary information: Supplementary material is available at Bioinformatics online.

Fig. 1.

Examples of a species tree (left), two gene trees (middle) and an adjacency tree (right). Blue dots are speciation nodes. Leaves are extant (species, genes, adjacencies), except the one labeled by a red cross (gene loss) or a red flash (breakage). Green squares are (gene or adjacency) duplication nodes. Gene labels refer to the species they belong to. Every node of the adjacency tree is labeled by a couple of nodes from gene trees

Fig. 2.

Example of the application of the algorithm on two genes trees, G₁ and G₂, a species tree S and an adjacency list shown on the line Input. The costs are C(Gain)= C(Break)= 1. All the costs c_b(E_i,E_j) are computed for b∈0,1, E ∈A,B,C, i,j ∈[1..8], with E_i in G₁ and E_j in G₂. As a result c₀(C₅,C₈) = 2 while c₁(C₅,C₈) = 1. Therefore, the adjacency forest on the line Output contains C₅C₈. The left tree has cost 0 while the right one costs C(Gain)= 1 for the gain of the adjacency B₁B₃

Fig. 3.

Proportion of genes having k neighbors, function of k. Red plain line is obtained with DeCo and PhylDog trees. Green dashed line is obtained with PhylDog trees and the pairwise alternative. Blue dotted line is obtained with TreeBeST trees and DeCo

Fig. 4.

Angiosperm and mammalian phylogenies, where branch lengths are proportional to the number of adjacency duplications normalized by the number of genes. The scale is indicated at the bottom left of the two figures