An approximation algorithm for genome sorting by reversals to recover all adjacencies

Shanshan Zhai, Peng Zhang, Daming Zhu, Weitian Tong, Yao Xu, Guohui Lin

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Genome rearrangement problems have been extensively studied for more than two decades, intended to understand the species evolutionary relationships in terms of the long range genetic mutations at the genome level. While most earlier studies focus on the simplified genomes ignoring gene duplicates, thousands of whole genome sequencing projects reveal that a genome typically carries multiple gene duplicates distributed in various ways along the genome. Given a source genome and a target genome such that one is a re-ordering of the genes in the other, we measure the evolutionary distance by the minimum number of reversals applied on the source genome to recover all the gene adjacencies in the target genome. We define this optimization problem as sorting by reversals to recover all adjacencies, or SBR2RA in short. We show that SBR2RA is APX-hard and uncover some similarities and differences to the classic counterpart, the sorting by reversals problem. From the approximability perspective, we present a 2 α-approximation algorithm, where α∈ [1 , 2] is the best approximation ratio for a related optimization problem which is suspected to be NP-hard.

Original languageEnglish
Pages (from-to)1170-1190
Number of pages21
JournalJournal of Combinatorial Optimization
Volume37
Issue number4
DOIs
StatePublished - May 1 2019

Keywords

  • Alternating cycle
  • Gene adjacency
  • Genome rearrangement
  • Maximum matching
  • Sorting by reversals

Fingerprint

Dive into the research topics of 'An approximation algorithm for genome sorting by reversals to recover all adjacencies'. Together they form a unique fingerprint.

Cite this