Sorting genomes with rearrangements and segmental duplications through trajectory graphs

We study the problem of sorting genomes under an evolutionary model that includes genomic rearrangements and segmental duplications. We propose an iterative algorithm to improve any initial evolutionary trajectory between two genomes in terms of parsimony. Our algorithm is based on a new graphical model, the trajectory graph, which models not only the final states of two genomes but also an existing evolutionary trajectory between them. We show that redundant rearrangements in the trajectory correspond to certain cycles in the trajectory graph, and prove that our algorithm converges to an optimal trajectory for any initial trajectory involving only rearrangements.


Published in:
BMC Bioinformatics, 14, Suppl. 15, S9
Presented at:
11th RECOMB Workshop on Comparative Genomics RECOMB-CG'13
Year:
2013
Publisher:
London, Biomed Central Ltd
ISSN:
1471-2105
Laboratories:




 Record created 2014-01-09, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)