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)

Abstract

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
PublisherSpringer
Pages93-107
Number of pages15
ISBN (Electronic)978-3-030-42266-0
ISBN (Print)978-3-030-42265-3
DOIs
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

Conference

Conference7th International Conference on Algorithms for Computational Biology, AlCoB 2020
CountryUnited States
CityMissoula
Period13/04/2015/04/20

Bibliographical note

Accepted author manuscript

Keywords

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

Fingerprint

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

Cite this