Journal Article
No Thumbnail Available
License
ClosedAccessClosed Access
 

Conflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks

Simple item page
cris.lastimport.scopus2024-02-12T19:34:44Z
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2021-10-04
dc.conference.datestart2021-08-02
dc.conference.placeVirtual
dc.conference.seriesWorkshop on Algorithms in Bioinformatics
dc.conference.seriesWorkshop on Algorithms in Bioinformatics
dc.conference.seriesshortcutWABI
dc.conference.shortcutWABI 2021
dc.conference.weblinkhttps://acm-bcb.org/WABI/2021/
dc.contributor.authorGórecki, Paweł
dc.contributor.authorMykowiecka, Agnieszka
dc.contributor.authorRutecka, Natalia
dc.contributor.authorDąbkowski, Dawid
dc.contributor.authorWawerka, Marcin
dc.date.accessioned2024-01-24T20:06:08Z
dc.date.available2024-01-24T20:06:08Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.WABI.2021.17
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/103531
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2021/14370/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages17:1--17:21
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enPhylogenetic Network
dc.subject.enGene Tree
dc.subject.enSpecies Tree
dc.subject.enDeep Coalescence
dc.subject.enReticulation
dc.subject.enOptimal Displayed Tree
dc.titleConflict Resolution Algorithms for Deep Coalescence Phylogenetic Networks
dc.typeJournalArticle
dspace.entity.typePublication