Solving the Tree Containment Problem Using Graph Neural Networks
<|reference_start|>Solving the Tree Containment Problem Using Graph Neural Networks: 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.<|reference_end|>
@article{dushatskiy2024solving,
    title={Solving the Tree Containment Problem Using Graph Neural Networks},
    author={Arkadiy Dushatskiy, Esther Julien, Leen Stougie, Leo van Iersel},
    journal={arXiv preprint arXiv:2404.09812},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.09812},
    primaryClass={q-bio.PE cs.LG}
}