DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2023.6

Simultaneous Reconstruction of Duplication Episodes and Gene-Species Mappings

Authors: Paweł Górecki, Natalia Rutecka, Agnieszka Mykowiecka, and Jarosław Paszek

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

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.

Cite as

Paweł Górecki, Natalia Rutecka, Agnieszka Mykowiecka, and Jarosław Paszek. Simultaneous Reconstruction of Duplication Episodes and Gene-Species Mappings. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.WABI.2023.6},
  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}
}

Document

DOI: 10.4230/LIPIcs.WABI.2021.17

Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks

Authors: Marcin Wawerka, Dawid Dąbkowski, Natalia Rutecka, Agnieszka Mykowiecka, and Paweł Górecki

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

Abstract

We address the problem of inferring an optimal tree displayed by a network, given a gene tree G and a tree-child network N, under the deep coalescence cost. We propose an O(|G||N|)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where |G| and |N| are the sizes of G and N, respectively. This algorithm has the ability to state whether the cost is exact or is a lower bound. In addition, our algorithm provides a set of reticulation edges that correspond to the obtained cost. If the cost is exact, the set induces an optimal displayed tree that yields the cost. If the cost is a lower bound, the set contains pairs of conflicting edges, that is, edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires 2^{r+1}-1 invocations of DP in the worst case, where r is a number of reticulations. We propose a similar O(2^k|G||N|)-time algorithm for level-k networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also show how our algorithms can be extended to a broader class of phylogenetic networks. Despite their exponential complexity in the worst case, our solutions perform significantly well on empirical and simulated datasets, thanks to the strategy of resolving internal dissimilarities between gene trees and networks. In particular, experiments on simulated data indicate that the runtime of our solution is Θ(2^{0.543 k}|G||N|) on average. Therefore, our solution is an efficient alternative to enumeration strategies commonly proposed in the literature and enables analyses of complex networks with dozens of reticulations.

Cite as

Marcin Wawerka, Dawid Dąbkowski, Natalia Rutecka, Agnieszka Mykowiecka, and Paweł Górecki. Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wawerka_et_al:LIPIcs.WABI.2021.17,
  author =	{Wawerka, Marcin and D\k{a}bkowski, Dawid and Rutecka, Natalia and Mykowiecka, Agnieszka and G\'{o}recki, Pawe{\l}},
  title =	{{Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.17},
  URN =		{urn:nbn:de:0030-drops-143708},
  doi =		{10.4230/LIPIcs.WABI.2021.17},
  annote =	{Keywords: Phylogenetic Network, Gene Tree, Species Tree, Deep Coalescence, Reticulation, Optimal Displayed Tree}
}

Document

DOI: 10.4230/LIPIcs.WABI.2017.5

Detecting Locus Acquisition Events in Gene Trees

Authors: Michal Aleksander Ciach, Anna Muszewska, and Pawel Górecki

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract

Horizontal Gene Transfer (HGT), a process of acquisition and fixation of foreign genetic material, is an important biological phenomenon. Several approaches to HGT inference have been proposed. However, most of them either rely on approximate, non-phylogenetic methods or on the tree reconciliation, which is computationally intensive and sensitive to parameter values. In this work, we investigate the Locus Tree Inference problem as a possible alternative that combines the advantages of both approaches. We show several algorithms to solve the problem in the parsimony framework. We introduce a novel tree mapping, which allows us to obtain a heuristic solution to the problems of locus tree inference and duplication classification. Our approach allows not only for faster comparisons of gene and species trees but also to improve known algorithms for duplication inference in the presence of polytomies in the species trees.

Cite as

Michal Aleksander Ciach, Anna Muszewska, and Pawel Górecki. Detecting Locus Acquisition Events in Gene Trees. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ciach_et_al:LIPIcs.WABI.2017.5,
  author =	{Ciach, Michal Aleksander and Muszewska, Anna and G\'{o}recki, Pawel},
  title =	{{Detecting Locus Acquisition Events in Gene Trees}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.5},
  URN =		{urn:nbn:de:0030-drops-76545},
  doi =		{10.4230/LIPIcs.WABI.2017.5},
  annote =	{Keywords: rank, taxon, ranked species tree, speciation, gene duplication, gene loss, horizontal gene transfer}
}

3 Search Results for "Górecki, Paweł"

Simultaneous Reconstruction of Duplication Episodes and Gene-Species Mappings

Abstract

Cite as

Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks

Abstract

Cite as

Detecting Locus Acquisition Events in Gene Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message