Linear time reconciliation with bounded transfers of genes

Tree reconciliation is a general framework for investigating the mutual influence between gene and species trees according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find a reconciliation of minimum total cost. The resulting optimization problem is known as the reconciliation problem. Usually, the considered events are: co-divergence, gene Duplication, horizontal gene Transfer, and gene Loss (DTL model), while in a more conservative setting, gene transfers are not allowed (DL model). The reconciliation problem requires, in the DL model, time linear in the dimension of the two trees and at least quadratic time in the DTL model. Hence, it is reasonable to argue that the introduction of horizontal gene transfers increases the complexity of the problem. Instead, we introduce horizontal gene transfers with some constraints and prove that the problem is still linear in the dimension of the trees. Namely, we allow gene transfers of length bounded by k = 2, on the basis of the observation that transfers are more likely to occur between closely related species than between distantly related ones. Then we extend the same reasonings to the case in which k > 2 under additional constrains. In this paper we study also another problem related to the reconciliation one, that is optimally rooting one of the two trees when it is not, and also for it we prove similar results. The relevance of this contribution lies in showing that, in the transit from the DL to the DTL model, the computational time does not increase suddenly to quadratic but remains linear in the case when gene transfers are very short (i.e. happening