Polyploid Arithmetic

Lafond, Manuel, Huber, Katharina ORCID: https://orcid.org/0000-0002-6368-7511 and Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 (2026) Polyploid Arithmetic. Bulletin of Mathematical Biology. ISSN 0092-8240 (In Press)

PDF (ploidy_profiles-accepted-2026-06-23) - Accepted Version Restricted to Repository staff only until 31 December 2099. Available under License Creative Commons Attribution. Request a copy

Abstract

Polyploidy occurs in plants and animals, and is an important force in speciation and genome evolution. The main focus of this paper is the following fundamental question that was recently posed by Huber and Maher: Given the ploidy numbers of a collection of extant species, or their {\em ploidy profile}, what is the smallest number of hybridizations needed in {\em any} evolutionary history for these species to completely represent these numbers? In this paper, we shall show that this question can be rephrased in terms of {\em addition chains} and the closely related {\em addition sequences}, which have been studied for over a century in mathematics and computer science. These are sequences of natural numbers that start with 1, so that each number in the sequence larger than 1 is the sum of two other numbers arising earlier in the sequence. In our first main result, we show that finding the smallest number of hybridization events to explain a ploidy profile, or the {\em hybrid number}, is equivalent to solving the so-called {\em addition sequence problem}. This immediately implies that computing the hybridization number is computationally intractable. Even so, it also leads to new connections to representing polyploid evolution using networks. More specifically, in our second main result we show that ploidy profiles representable by {\em tree-child networks} are exactly the addition chains, implying a polynomial-time algorithm for identifying these profiles. We then consider {\em beaded tree-child networks}, which permit the representation of autopolyploidy events, and in our third main result we provide a greedy polynomial-time algorithm to decide whether a given profile can be realized by such a network. We expect that our results can be leveraged in future work through, for example, making use of known algorithms for computing short addition sequences to give bounds for the hybrid number, and in guiding network reconstruction for polyploid species.

Item Type:	Article
Uncontrolled Keywords:	polyploidy,phylogenetic networks,addition chains,algorithms
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	LivePure Connector
Date Deposited:	07 Jul 2026 16:33
Last Modified:	22 Jul 2026 11:53
URI:	https://ueaeprints.uea.ac.uk/id/eprint/103782
DOI:	issn:0092-8240

Actions (login required)

View Item