Minimizing genomic duplication episodes. (December 2020)

• Record Type: Journal Article
• Authors: Paszek, Jarosław; Tiuryn, Jerzy; Górecki, Paweł
• Is Part Of: Computational biology and chemistry. Volume 89(2020)
• Publication Date: 2020-12
• Subjects: Genomic duplication -- Duplication episode -- Minimum episodes problem -- Reconciliation -- Maximal path -- Species tree; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2020.107260
• Languages: English
• ISSNs: 1476-9271

Abstract

Graphical abstract: Highlights: Genomic duplication inference from a set of rooted gene trees and a species tree. Model of scenarios preserving the minimal number of single gene duplications. Polynomial time algorithm to compute Maximal Path (MP-score) of duplication clusters. A correspondence between algorithms for computing M P and minimum episodes (ME) score. MP-optimal mappings support duplication episodes from ME-optimal mappings. Abstract: Background: The genomic duplication study is fundamental to understand the process of evolution. In evolutionary molecular biology, many approaches focus on discovering the occurrences of gene duplications and multiple gene duplication episodes and their locations in the Tree of Life. To reconstruct such episodes, one can cluster single gene duplications inferred by reconciling a set of gene trees with a species tree. Results: We propose an efficient quadratic time algorithm to solve the problem of genomic duplication clustering, in which input gene trees are rooted, episode locations are restricted to preserve the minimal number of single gene duplications, clustering rules are described by minimum episodes method, and the goal is based on the recently introduced new approach to minimize the maximal number of duplication episodes on a single path, called here the M P score. Based on our theoretical results, we show new algorithmic relationships between the M P score and the minimum episodes ( M E ) score, defined as the minimal number of duplication episodes. Conclusions: Our evaluation analysis on three empirical datasets demonstrates, that under the model in which the minimal number of duplications is preserved, the duplication clusterings with minimal M P score support the clusterings with the minimal total number of duplication episodes. Availability: The software is available at https://bitbucket.org/pgor17/rmp .