Polyploidy Arithmetic.
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 ploidy profile, what is the smallest number of hybridizations needed in 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 addition chains and the closely related 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 hybrid number, is equivalent to solving the so-called 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 tree-child networks are exactly the addition chains, implying a polynomial-time algorithm for identifying these profiles. We then consider 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.