Exploring the space of gene/species reconciliations with transfers

Chan, Yao-ban, Ranwez, Vincent and Scornavacca, Céline (2014) Exploring the space of gene/species reconciliations with transfers. Journal of Mathematical Biology, 71 5: 1179-1209. doi:10.1007/s00285-014-0851-2


Author Chan, Yao-ban
Ranwez, Vincent
Scornavacca, Céline
Title Exploring the space of gene/species reconciliations with transfers
Journal name Journal of Mathematical Biology   Check publisher's open access policy
ISSN 0303-6812
1432-1416
Publication date 2014-12-01
Year available 2014
Sub-type Article (original research)
DOI 10.1007/s00285-014-0851-2
Open Access Status Not yet assessed
Volume 71
Issue 5
Start page 1179
End page 1209
Total pages 31
Place of publication Heidelberg, Germany
Publisher Springer
Language eng
Formatted abstract
Reconciliations between gene and species trees have important applications in the study of genome evolution (e.g. sequence orthology prediction or quantification of transfer events). While numerous methods have been proposed to infer them, little has been done to study the underlying reconciliation space. In this paper, we characterise the reconciliation space for two evolutionary models: the DTL (duplication, loss and transfer) model and a variant of it—the no-TL model—which does not allow TL events (a transfer immediately followed by a loss). We provide formulae to compute the size of the corresponding spaces and define a set of transformation operators sufficient to explore the entire reconciliation space. We also define a distance between two reconciliations as the minimal number of operations needed to transform one into the other and prove that this distance is easily computable in the no-TL model. Computing this distance in the DTL model is more difficult and it is an open question whether it is NP-hard or not. This work constitutes an important step toward reconciliation space characterisation and reconciliation comparison, needed to better assess the performance of reconciliation inference methods through simulations
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2015 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 2 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 13 Sep 2013, 02:47:42 EST by Kay Mackie on behalf of School of Mathematics & Physics