11 papers
NOC NOC, who's there? Clustering systems of tree-child and normal networks
Anna Lindeberg, Marc Hellmuth
Clustering systems provide a natural way to encode structural information contained in phylogenetic networks. In this note, we study the clustering systems of normal and tree-child…
Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors
Patricia A. Ebert, Anna Lindeberg, Marc Hellmuth
Evolutionary histories are often represented by rooted phylogenetic networks, whose leaves correspond to extant taxa and whose internal vertices represent ancestral lineages. Since…
Encoding Phylogenetic Networks with Least Common Ancestor Constraints
Marc Hellmuth, Anna Lindeberg, Vincent Moulton
Encoding phylogenetic networks by suitable substructures is a central problem in phylogenetic combinatorics. We study encodings based on least common ancestor (LCA) constraints. Fo…
Regularizing and Normalizing DAGs and Phylogenetic Networks
Marc Hellmuth, Anna Lindeberg, Vincent Moulton
Phylogenetic networks and, more generally, directed acyclic graphs (DAGs) represent hierarchical structure beyond trees, for instance in the presence of reticulate evolutionary eve…
Inferring DAGs and Phylogenetic Networks from Least Common Ancestors
Anna Lindeberg, Anton Alfonsson, Vincent Moulton +2
A least common ancestor (LCA) of two leaves in a directed acyclic graph (DAG) is a vertex that is an ancestor of both leaves and has no proper descendant that is also their common…
Global Least Common Ancestor (LCA) Networks
Anna Lindeberg, Bruno J. Schmidt, Manoj Changat +3
Directed acyclic graphs (DAGs) are fundamental structures used across many scientific fields. A key concept in DAGs is the least common ancestor (LCA), which plays a crucial role i…
Orthology and Near-Cographs in the Context of Phylogenetic Networks
Anna Lindeberg, Guillaume E. Scholz, Nicolas Wieseke +1
Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of o…
Characterizing and Transforming DAGs within the I-LCA Framework
Marc Hellmuth, Anna Lindeberg
We explore the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs), focusing on the interplay between so-called -lca-relevant DAGs a…
Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
Anna Lindeberg, Marc Hellmuth
Rooted phylogenetic networks, or more generally, directed acyclic graphs (DAGs), are widely used to model species or gene relationships that traditional rooted trees cannot fully c…
Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective
Anna Lindeberg, Guillaume E. Scholz, Marc Hellmuth
In phylogenetics, reconstructing rooted trees from distances between taxa is a common task. Böcker and Dress generalized this concept by introducing symbolic dated maps $δ:X \times…
Isomorphism Testing of Rooted Trees in Linear Time
Anna Lindeberg
The AHU-algorithm solves the computationally difficult graph isomorphism problem for rooted trees, and does so with a linear time complexity. Although the AHU-algorithm has remaine…