A QUBO Formulation for the Tree Containment Problem

Show simple item record

dc.contributor.author Dinneen, MJ en
dc.contributor.author Ghodla, PS en
dc.contributor.author Linz, S en
dc.date.accessioned 2023-01-24T23:04:43Z
dc.date.available 2023-01-24T23:04:43Z
dc.date.issued 2022 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-560 (2022) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri https://hdl.handle.net/2292/62555
dc.description.abstract to represent the evolutionary relationships between entities such as species, languages, cancer cells, and viruses. To reconstruct and analyze phylogenetic networks, the problem of deciding whether or not a given rooted phylogenetic network embeds a given rooted phylogenetic tree is of recurring interest. This problem, formally know as Tree Containment, is NP-complete in general and polynomial-time solvable for certain classes of phylogenetic networks. In this paper, we connect ideas from quantum computing and phylogenetics to present an efficient Quadratic Unconstrained Binary Optimization formulation for Tree Containment in the general setting. For an instance (N, T ) of Tree Containment, where N is a phylogenetic network with nN vertices and T is a phylogenetic tree with nT vertices, the number of logical qubits that are required for our formulation is O(nNnT ).
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php en
dc.title A QUBO Formulation for the Tree Containment Problem en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder Copyright: The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace