Gene order alignment on trees with multiOrthoAlign

BMC Genomics

Research

Nadia El-Mabrouk¹  Billel Benzaid¹ 

[1] Département d'Informatique (DIRO), Université de Montréal, H3C3J7, Montréal, Québec, Canada;

关键词: Gene Order;    Internal Node;    Maximum Cardinality;    Ancestral Genome;    Visible History;   

DOI  :  10.1186/1471-2164-15-S6-S5

来源: Springer

【 摘 要 】

We relate the comparison of gene orders to an alignment problem. Our evolutionary model accounts for both rearrangement and content-modifying events. We present a heuristic based on dynamic programming for the inference of the median of three genomes and apply it in a phylogenetic framework. multiOrthoAlign is shown accurate on simulated and real datasets, and shown to significantly improve the running-time of DupLoCut, an "almost" exact algorithm based on linear programming, developed recently for the same problem.

【 授权许可】

CC BY   
© Benzaid and El-Mabrouk; licensee BioMed Central Ltd. 2014