Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models (Q2303740)

The paper presents the first results of counting and sampling evolutionary scenarios in models that take into account duplication of genes, loss of genes, and HGT. The originality of the work lies in the fact that authors believe that only a species tree is given, and thus consider all possible evolutionary histories of a given size, i.e., leading to a given number of genes. The results include formal grammars describing this combinatorial space, as well as counting and sampling algorithms obtained using dynamic programming methods or combinatorics. On the basis of the proposed method, the exact asymptotic is obtained by the number of stories for two specific tree species, a rooted caterpillar and a complete binary tree in the DL model without markup, although the method is also applicable to any given tree of species in this model. Counting and sampling algorithms have complemented these results for other models, especially models that take into account HGT. The experimental results give the first global view of the potential space of evolutionary stories for a given tree species. They confirm the expected fact that the introduction of HGT in the model leads to a significant increase in the space of possible stories; they also lead to an interesting observation that in a ranked DLT model, the total number of stories is asymptotically almost independent of a given species tree.