The Gene Family-Free Median of Three

The gene family-free framework for comparative genomics aims at developing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We show that the corresponding computational problem is MAX SNP-hard and we present a 0-1 linear program for its exact solution. The result of this program is a median genome with median genes associated to extant genes, in which median adjacencies are assumed to define positional orthologs. We demonstrate through simulations and comparison with the OMA orthology database that the herein presented method is able compute accurate medians and positional orthologs for genomes comparable in size of bacterial genomes.


Editor(s):
Frith, M
Pedersen, Cns
Published in:
Proceedings of the 16th International Workshop on Algorithms in Bioinformatics (WABI'16), 102-120
Presented at:
16th International Workshop on Algorithms in Bioinformatics (WABI'16)
Year:
2016
Publisher:
Springer AG
ISBN:
978-3-319-43681-4
978-3-319-43680-7
Laboratories:




 Record created 2017-01-24, last modified 2018-05-07


Rate this document:

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