Solving the Tree Containment Problem Using Graph Neural Networks
Arkadiy Dushatskiy Esther Julien Leo van Iersel Leen Stougie
Tree Containment is a fundamental problem in phylogenetics useful for
verifying a proposed phylogenetic network, representing the evolutionary
history of certain species. Tree Containment asks whether the given
phylogenetic tree (for instance, constructed from a DNA fragment showing
tree-like evolution) is contained in the given phylogenetic network. In the
general case, this is an NP-complete problem. We propose to solve it
approximately using Graph Neural Networks. In particular, we propose to combine
the given network and the tree and apply a Graph Neural Network to this
network-tree graph. This way, we achieve the capability of solving the tree
containment instances representing a larger number of species than the
instances contained in the training dataset (i.e., our algorithm has the
inductive learning ability). Our algorithm demonstrates an accuracy of over
$95\%$ in solving the tree containment problem on instances with up to 100
leaves.