On the domination number of $t$-constrained de Bruijn graphs

Autor: Tiziana Calamoneri, Angelo Monti, Blerina Sinaimeri

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no 2, Iss Graph Theory (2022)

Motivated by the work on the domination number of directed de Bruijn graphs and some of its generalizations, in this paper we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely $t$-constrained de Bruijn graphs, w

Externí odkaz: https://doaj.org/article/87d9a1d897184bf8a9299d3743519832

A General Framework for Enumerating Equivalence Classes of Solutions

Autor: Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri

Publikováno v: ESA 2021-29th Annual European Symposium on Algorithms
ESA 2021-29th Annual European Symposium on Algorithms, Sep 2021, Virtual, Portugal. pp.1-14, ⟨10.4230/LIPIcs.ESA.2021.80⟩

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5e987d15765a61f5c7370ad944dc5c24
https://doi.org/10.1007/s00453-023-01131-1

A Family of Tree-Based Generators for Bubbles in Directed Graphs

Autor: Leandro Lima, Giuseppe F. Italiano, Luca Pepè Sciarria, Marie-France Sagot, Blerina Sinaimeri, Vicente Acuña

Publikováno v: Combinatorial Algorithms
IWOCA 2020-31st International Workshop on Combinatorial Algorithms
IWOCA 2020-31st International Workshop on Combinatorial Algorithms, Jun 2020, Bordeaux, France. pp.17-29, ⟨10.1007/978-3-030-48966-3_2⟩
Journal of Graph Algorithms and Applications
Journal of Graph Algorithms and Applications, 2021, 25 (1), pp.549-562. ⟨10.7155/jgaa.00572⟩
Journal of Graph Algorithms and Applications, Brown University, 2021, 25 (1), pp.549-562. ⟨10.7155/jgaa.00571⟩
Lecture Notes in Computer Science ISBN: 9783030489656
IWOCA

International audience; Bubbles are pairs of internally vertex-disjoint (s, t)-paths in a directed graph. In de Bruijn graphs built from reads of RNA and DNA data, bubbles represent interesting biological events, such as alternative splicing (AS) and

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6d9e2dfc9e580c318ce416bc3b301441
http://europepmc.org/articles/PMC7254895

Efficiently sparse listing of classes of optimal cophylogeny reconciliations

Autor: Marie-France Sagot, Yishu Wang, Blerina Sinaimeri, Arnaud Mary

Publikováno v: Algorithms for Molecular Biology
Algorithms for Molecular Biology, 2022, 17 (1), pp.1-16. ⟨10.1186/s13015-022-00206-y⟩

Background Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenar

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ae6f6c15271e0a1fe6a4fe19e20990e
https://pubmed.ncbi.nlm.nih.gov/35168648

Capybara: Equivalence ClAss enumeration of coPhylogenY event-BAsed ReconciliAtions

Autor: Yishu Wang, Blerina Sinaimeri, Marie-France Sagot, Arnaud Mary

Publikováno v: Bioinformatics
Bioinformatics, Oxford University Press (OUP), 2020, 36 (14), pp.4197-4199. ⟨10.1093/bioinformatics/btaa498⟩
Bioinformatics, 2020, 36 (14), pp.4197-4199. ⟨10.1093/bioinformatics/btaa498⟩

Motivation Phylogenetic tree reconciliation is the method of choice in analyzing host-symbiont systems. Despite the many reconciliation tools that have been proposed in the literature, two main issues remain unresolved: (i) listing suboptimal solutio

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a13cefbc2984b328ba337c7606389d5c
http://hdl.handle.net/11385/202461