Linear Time Algorithm for Tree-Child Network Containment

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Citations (Scopus)
5 Downloads (Pure)


Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks, to distinguish different networks, and to see when one network is embedded in another. Here, we consider the Network Containment problem, which asks whether a given network is contained in another network. We give a linear-time algorithm to this problem for the class of tree-child networks using the recently introduced tree-child sequences by Linz and Semple. We implement this algorithm in Python and show that the linear-time theoretical bound on the input size is achievable in practice.

Original languageEnglish
Title of host publicationAlgorithms for Computational Biology
Subtitle of host publication7th International Conference, AlCoB 2020, Proceedings
EditorsCarlos Martín-Vide, Miguel A. Vega-Rodríguez, Travis Wheeler
Place of PublicationCham
Number of pages15
ISBN (Electronic)978-3-030-42266-0
ISBN (Print)978-3-030-42265-3
Publication statusPublished - 2020
Event7th International Conference on Algorithms for Computational Biology, AlCoB 2020 - Missoula, United States
Duration: 13 Apr 202015 Apr 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12099 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Algorithms for Computational Biology, AlCoB 2020
CountryUnited States

Bibliographical note

Accepted author manuscript


  • Network Containment
  • Phylogenetics
  • Tree-child networks
  • Tree-child sequences


Dive into the research topics of 'Linear Time Algorithm for Tree-Child Network Containment'. Together they form a unique fingerprint.

Cite this