Bioinformatický seminár

Tue 29 Nov. 2011, 17:20
I-9

Title: Tofigh et al. Simultaneous Identification of Duplications and Lateral Gene Transfers
Speaker: Pavol Hudec, Robert Mauer

The incongruency between a gene tree and a corresponding species tree can be 
attributed to evolutionary events such as gene duplication and gene loss. 
This paper describes a combinatorial model where so-called DTL-scenarios are 
used to explain the differences between a gene tree and a corresponding 
species tree taking into account gene duplications, gene losses, and lateral 
gene transfers (also known as horizontal gene transfers). The reasonable 
biological constraint that a lateral gene transfer may only occur between 
contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony 
methods are introduced by defining appropriate optimization problems. We 
show that finding most parsimonious acyclic DTL-scenarios is NP-hard. 
However, by dropping the condition of acyclicity, the problem becomes 
tractable, and we provide a dynamic programming algorithm as well as a fixed-
parameter-tractable algorithm for finding most parsimonious DTL-scenarios.