Minimizing the deep coalescence cost

Metagenomic studies identify the species present in an environmental sample usually by using procedures that match molecular sequences, e.g. genes, with the species taxonomy. Here, we first formulate the problem of gene-species matching in the parsimony framework using binary phylogenetic gene and species trees under the deep coalescence cost and the assumption that each gene is paired uniquely with one species. In particular, we solve the problem in the cases when one of the trees is a caterpillar. Next, we propose a dynamic programming algorithm, which solves the problem exactly, however, its time and space complexity is exponential. Next, we generalize the problem to include non-binary trees and show the solution for caterpillar trees. We then propose time and space-efficient heuristic algorithms for solving the gene-species matching problem for any input trees. Finally, we present the results of computational experiments on simulated and empirical datasets consisting of binary tree pairs.