Publication Details

Reference Category Journals
DOI / URL link
Title (Primary) A probabilistic version of Sankoff’s maximum parsimony algorithm
Author Balogh, G.; Bernhart, S.H.; Stadler, P.F.; Schor, J.;
Journal Journal of Bioinformatics and Computational Biology
Year 2020
Department MOLSYB;
Volume 18
Issue 1
Language englisch;
POF III (all) F11;
Keywords Sankoff’s parsimony algorithm; gene family evolution; partition function; microRNA evolution; ePoPE
Abstract

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.

ID 23122
Persistent UFZ Identifier https://www.ufz.de/index.php?en=20939&ufzPublicationIdentifier=23122
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