Linear Time Algorithm for Tree-Child Network Containment

Remie Janssen; Yukihiro Murakami

doi:10.1007/978-3-030-42266-0_8

Linear Time Algorithm for Tree-Child Network Containment

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

5 Citations (Scopus)

45 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 language	English
Title of host publication	Algorithms for Computational Biology
Subtitle of host publication	7th International Conference, AlCoB 2020, Proceedings
Editors	Carlos Martín-Vide, Miguel A. Vega-Rodríguez, Travis Wheeler
Place of Publication	Cham
Publisher	Springer
Pages	93-107
Number of pages	15
ISBN (Electronic)	978-3-030-42266-0
ISBN (Print)	978-3-030-42265-3
DOIs	https://doi.org/10.1007/978-3-030-42266-0_8
Publication status	Published - 2020
Event	7th International Conference on Algorithms for Computational Biology, AlCoB 2020 - Missoula, United States Duration: 13 Apr 2020 → 15 Apr 2020

Publication series

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

Conference

Conference	7th International Conference on Algorithms for Computational Biology, AlCoB 2020
Country/Territory	United States
City	Missoula
Period	13/04/20 → 15/04/20

Bibliographical note

Accepted author manuscript

Keywords

Network Containment
Phylogenetics
Tree-child networks
Tree-child sequences

Access to Document

10.1007/978-3-030-42266-0_8

Network_Containment_AlCoB_2020Accepted author manuscript, 483 KB

Cite this

Janssen, R., & Murakami, Y. (2020). Linear Time Algorithm for Tree-Child Network Containment. In C. Martín-Vide, M. A. Vega-Rodríguez, & T. Wheeler (Eds.), Algorithms for Computational Biology : 7th International Conference, AlCoB 2020, Proceedings (pp. 93-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12099 LNBI). Springer. https://doi.org/10.1007/978-3-030-42266-0_8

Janssen, Remie ; Murakami, Yukihiro. / Linear Time Algorithm for Tree-Child Network Containment. Algorithms for Computational Biology : 7th International Conference, AlCoB 2020, Proceedings. editor / Carlos Martín-Vide ; Miguel A. Vega-Rodríguez ; Travis Wheeler. Cham : Springer, 2020. pp. 93-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f2a7ebe761774a18ade8af8db1c34e3a,

title = "Linear Time Algorithm for Tree-Child Network Containment",

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.",

keywords = "Network Containment, Phylogenetics, Tree-child networks, Tree-child sequences",

author = "Remie Janssen and Yukihiro Murakami",

note = "Accepted author manuscript; 7th International Conference on Algorithms for Computational Biology, AlCoB 2020 ; Conference date: 13-04-2020 Through 15-04-2020",

year = "2020",

doi = "10.1007/978-3-030-42266-0_8",

language = "English",

isbn = "978-3-030-42265-3",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "93--107",

editor = "Carlos Mart{\'i}n-Vide and Vega-Rodr{\'i}guez, {Miguel A.} and Travis Wheeler",

booktitle = "Algorithms for Computational Biology",

}

Janssen, R & Murakami, Y 2020, Linear Time Algorithm for Tree-Child Network Containment. in C Martín-Vide, MA Vega-Rodríguez & T Wheeler (eds), Algorithms for Computational Biology : 7th International Conference, AlCoB 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12099 LNBI, Springer, Cham, pp. 93-107, 7th International Conference on Algorithms for Computational Biology, AlCoB 2020, Missoula, United States, 13/04/20. https://doi.org/10.1007/978-3-030-42266-0_8

Linear Time Algorithm for Tree-Child Network Containment. / Janssen, Remie; Murakami, Yukihiro.
Algorithms for Computational Biology : 7th International Conference, AlCoB 2020, Proceedings. ed. / Carlos Martín-Vide; Miguel A. Vega-Rodríguez; Travis Wheeler. Cham: Springer, 2020. p. 93-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12099 LNBI).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Linear Time Algorithm for Tree-Child Network Containment

AU - Janssen, Remie

AU - Murakami, Yukihiro

N1 - Accepted author manuscript

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Network Containment

KW - Phylogenetics

KW - Tree-child networks

KW - Tree-child sequences

UR - http://www.scopus.com/inward/record.url?scp=85083031400&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-42266-0_8

DO - 10.1007/978-3-030-42266-0_8

M3 - Conference contribution

AN - SCOPUS:85083031400

SN - 978-3-030-42265-3

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 93

EP - 107

BT - Algorithms for Computational Biology

A2 - Martín-Vide, Carlos

A2 - Vega-Rodríguez, Miguel A.

A2 - Wheeler, Travis

PB - Springer

CY - Cham

T2 - 7th International Conference on Algorithms for Computational Biology, AlCoB 2020

Y2 - 13 April 2020 through 15 April 2020

ER -

Janssen R, Murakami Y. Linear Time Algorithm for Tree-Child Network Containment. In Martín-Vide C, Vega-Rodríguez MA, Wheeler T, editors, Algorithms for Computational Biology : 7th International Conference, AlCoB 2020, Proceedings. Cham: Springer. 2020. p. 93-107. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-42266-0_8

Linear Time Algorithm for Tree-Child Network Containment

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this