title: An O([Formula: see text]) algorithm for sorting signed genomes by reversals, transpositions, transreversals and block-interchanges.
abstract: We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges. The problem arises in the study of species evolution via large-scale genome rearrangement operations. Recently, Hao et al. gave a 2-approximation scheme called genome sorting by bridges (GSB) for solving this problem. Their result extended and unified the results of (i) He and Chen - a 2-approximation algorithm allowing reversals, transpositions, and block-interchanges (by also allowing transversals) and (ii) Hartman and Sharan - a 1.5-approximation algorithm allowing reversals, transpositions, and transversals (by also allowing block-interchanges). The GSB result is based on introduction of three bridge structures in the breakpoint graph, the L-bridge, T-bridge, and X-bridge that models goodreversal, transposition/transreversal, and block-interchange, respectively. However, the paper by Hao et al. focused on proving the 2-approximation GSB scheme and only mention a straightforward [Formula: see text] algorithm. In this paper, we give an [Formula: see text] algorithm for implementing the GSB scheme. The key idea behind our faster GSB algorithm is to represent cycles in the breakpoint graph by their canonical sequences, which greatly simplifies the search for these bridge structures. We also give some comparison results (running time and computed distances) against the original GSB implementation.
authors.affiliation: * Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore 117417, Republic of Singapore.
authors.forename: Shuzhi
authors.initials: S
authors.lastname: Yu
authors.affiliation: † School of Information and Key Laboratory of Evidence-Identifying in Universities of Shandong, Shandong University of Political Science and Law, Jinan, Shandong 250014, P. R. China.
authors.forename: Fanchang
authors.initials: F
authors.lastname: Hao
authors.affiliation: * Department of Computer Science, National University of Singapore, 13 Computing Drive, Singapore 117417, Republic of Singapore.
authors.forename: Hon Wai
authors.initials: HW
authors.lastname: Leong
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D004251:DNA Transposable Elements; D016678:Genome; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic
chemical_list: D004251:DNA Transposable Elements
keywords: Algorithm; approximation algorithm; block-interchange; genome rearrangement; genome sorting; reversal; transposition; transreversal