License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2023.6
URN: urn:nbn:de:0030-drops-186329
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18632/
Górecki, Paweł ;
Rutecka, Natalia ;
Mykowiecka, Agnieszka ;
Paszek, Jarosław
Simultaneous Reconstruction of Duplication Episodes and Gene-Species Mappings
Abstract
We present a novel problem, called MetaEC, which aims to infer gene-species assignments in a collection of gene trees with missing labels by minimizing the size of duplication episode clustering (EC). This problem is particularly relevant in metagenomics, where incomplete data often poses a challenge in the accurate reconstruction of gene histories. To solve MetaEC, we propose a polynomial time dynamic programming (DP) formulation that verifies the existence of a set of duplication episodes from a predefined set of episode candidates. We then demonstrate how to use DP to design an algorithm that solves MetaEC. Although the algorithm is exponential in the worst case, we introduce a heuristic modification of the algorithm that provides a solution with the knowledge that it is exact. To evaluate our method, we perform two computational experiments on simulated and empirical data containing whole genome duplication events, showing that our algorithm is able to accurately infer the corresponding events.
BibTeX - Entry
@InProceedings{gorecki_et_al:LIPIcs.WABI.2023.6,
author = {G\'{o}recki, Pawe{\l} and Rutecka, Natalia and Mykowiecka, Agnieszka and Paszek, Jaros{\l}aw},
title = {{Simultaneous Reconstruction of Duplication Episodes and Gene-Species Mappings}},
booktitle = {23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
pages = {6:1--6:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-294-5},
ISSN = {1868-8969},
year = {2023},
volume = {273},
editor = {Belazzougui, Djamal and Ouangraoua, A\"{i}da},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18632},
URN = {urn:nbn:de:0030-drops-186329},
doi = {10.4230/LIPIcs.WABI.2023.6},
annote = {Keywords: Genomic Duplication, Gene-Species Mapping, Duplication Episode, Gene Tree, Species Tree}
}
