H-trees: a Model of Evolutionary Scenarios with Horizontal Gene Transfer

Issue title: From Mathematical Beauty to the Truth of Nature: to Jerzy Tiuryn on his 60th Birthday

Article type: Research Article

Authors: Górecki, Paweł

Affiliations: Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. gorecki@mimuw.edu.pl

Note: [] Address for correspondence: Warsaw University, Institute of Informatics, Banacha 2, 02-097 Warsaw, Poland

Abstract: In this paper, we present a model of evolution of genes in the context of evolution of species. The concept is based on reconciliation models. We assume that the gene evolution is modeled by macro-evolutionary events like gene duplications, losses and horizontal gene transfers (HGTs) while the evolution of species is shaped by speciation events. We define an evolutionary scenario (called an H-tree) which will represent the common evolution of genes and species. We propose a rewrite system for transforming the scenarios. We prove that the system is confluent, sound and strongly normalizing. We show that a scenario in a normal form (that is, non-reducible) is unique and minimal in the sense of the cost computed as the total number of gene duplications, losses and HGTs (mutation cost). We present a classification of the scenarios and analyze their hierarchies.

Keywords: Rewrite system, Molecular evolution, Phylogenetic tree, Duplication-loss model (DL-model), Horizontal gene transfer, Reconciled tree

DOI: 10.3233/FI-2010-321

Journal: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 105-128, 2010