Minimising the Deep Coalescence

EasyChair Preprint 636

Abstract

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 formulate the problem of gene-species matching in the parsimony framework using 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 caterpillar. Next, we generalize the solution and propose several heuristic algorithms. Finally, we present the results of computational experiments on simulated and empirical datasets.

Keyphrases: deep coalescence, gene tree, metagenomics, species taxonomy

@booklet{EasyChair:636,
  author    = {Dawid Dąbkowski and Pawel Gorecki},
  title     = {Minimising the Deep Coalescence},
  doi       = {10.29007/r179},
  howpublished = {EasyChair Preprint 636},
  year      = {EasyChair, 2018}}