title: Computing the reversal distance between genomes in the presence of multi-gene families via binary integer programming.
abstract: Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting signed genomic data. Their algorithm determines the minimum number of reversals required for rearranging a genome to another -but only in the absence of gene duplicates. However, duplicates often account for 40% of a genome. In this paper, we show how to extend Hannenhalli and Pevzner's approach to deal with genomes with multi-gene families. We propose a new heuristic algorithm to compute the nearest reversal distance between two genomes with multi-gene families via binary integer programming. The experimental results on both synthetic and real biological data demonstrate that the proposed algorithm is able to find the reversal distance with high accuracy.
authors.affiliation: Advanced Virtual and Intelligent Computing Center, Department of Mathematics, Chulalongkorn University, Bangkok 10330, Thailand. jakkaman@hotmail.com
authors.forename: Jakkarin
authors.initials: J
authors.lastname: Suksawatchon
authors.forename: Chidchanok
authors.initials: C
authors.lastname: Lursinsap
authors.forename: Mikael
authors.initials: M
authors.lastname: Bodén
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D008957:Models, Genetic; D008969:Molecular Sequence Data; D005810:Multigene Family / Q000235:genetics*; D011382:Programming, Linear; D017422:Sequence Analysis, DNA / Q000379:methods*