Publication Details

Category Text Publication
Reference Category Journals
DOI 10.1142/S0219720020500043
Title (Primary) A probabilistic version of Sankoff’s maximum parsimony algorithm
Author Balogh, G.; Bernhart, S.H.; Stadler, P.F.; Schor, J.
Source Titel Journal of Bioinformatics and Computational Biology
Year 2020
Department MOLSYB
Volume 18
Issue 1
Page From art. 2050004
Language englisch
Keywords Sankoff’s parsimony algorithm; gene family evolution; partition function; microRNA evolution; ePoPE

The number of genes belonging to a multi-gene family usually varies substantially over their evolutionary history as a consequence of gene duplications and losses. A first step toward analyzing these histories in detail is the inference of the changes in copy number that take place along the individual edges of the underlying phylogenetic tree. The corresponding maximum parsimony minimizes the total number of changes along the edges of the species tree. Incorrectly determined numbers of family members however may influence the estimates drastically. We therefore augment the analysis by introducing a probabilistic model that also considers suboptimal assignments of changes. Technically, this amounts to a partition function variant of Sankoff’s parsimony algorithm. As a showcase application, we reanalyze the gain and loss patterns of metazoan microRNA families. As expected, the differences between the probabilistic and the parsimony method is moderate, in this limit of T→0, i.e. very little tolerance for deviations from parsimony, the total number of reconstructed changes is the same. However, we find that the partition function approach systematically predicts fewer gains and more loss events, showing that the data admit co-optimal solutions among which the parsimony approach selects biased representatives.

Persistent UFZ Identifier
Balogh, G., Bernhart, S.H., Stadler, P.F., Schor, J. (2020):
A probabilistic version of Sankoff’s maximum parsimony algorithm
J. Bioinform. Comput. Biol. 18 (1), art. 2050004 10.1142/S0219720020500043