Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0001-9664-1918
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
2025 (English)In: Bulletin of Mathematical Biology, ISSN 0092-8240, E-ISSN 1522-9602, Vol. 87, no 3, article id 44Article in journal (Refereed) Published
Abstract [en]

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 capture, especially in the presence of reticulate processes or horizontal gene transfers. Such networks or DAGs are typically inferred from observable data (e.g., genomic sequences of extant species), providing only an estimate of the true evolutionary history. However, these inferred DAGs are often complex and difficult to interpret. In particular, many contain vertices that do not serve as least common ancestors (LCAs) for any subset of the underlying genes or species, thus may lack direct support from the observable data. In contrast, LCA vertices are witnessed by historical traces justifying their existence and thus represent ancestral states substantiated by the data. To reduce unnecessary complexity and eliminate unsupported vertices, we aim to simplify a DAG to retain only LCA vertices while preserving essential evolutionary information. In this paper, we characterize LCA -relevant and lca -relevant DAGs, defined as those in which every vertex serves as an LCA (or unique LCA) for some subset of taxa. We introduce methods to identify LCAs in DAGs and efficiently transform any DAG into an LCA -relevant or lca -relevant one while preserving key structural properties of the original DAG or network. This transformation is achieved using a simple operator "⊖" that mimics vertex suppression. 

Place, publisher, year, edition, pages
2025. Vol. 87, no 3, article id 44
Keywords [en]
Algorithms, Cluster, Hasse diagram, NP-completeness, Phylogenetic networks, Regular DAGs, Reticulate evolution, Transformation
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-241740DOI: 10.1007/s11538-025-01419-zISI: 001420922600001PubMedID: 39937386Scopus ID: 2-s2.0-85218478616OAI: oai:DiVA.org:su-241740DiVA, id: diva2:1950188
Available from: 2025-04-05 Created: 2025-04-05 Last updated: 2025-04-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textPubMedScopus

Authority records

Lindeberg, AnnaHellmuth, Marc

Search in DiVA

By author/editor
Lindeberg, AnnaHellmuth, Marc
By organisation
Department of Mathematics
In the same journal
Bulletin of Mathematical Biology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
pubmed
urn-nbn

Altmetric score

doi
pubmed
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf