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

Shanshan Zhai (), Peng Zhang (), Daming Zhu (), Weitian Tong (), Yao Xu () and Guohui Lin ()
Additional contact information
Shanshan Zhai: Shandong University
Peng Zhang: Shandong University
Daming Zhu: Shandong University
Weitian Tong: Georgia Southern University
Yao Xu: University of Alberta
Guohui Lin: University of Alberta

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 5, 1170-1190

Abstract: 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 \alpha $$ 2 α -approximation algorithm, where $$\alpha \in [1, 2]$$ α ∈ [ 1 , 2 ] is the best approximation ratio for a related optimization problem which is suspected to be NP-hard.

Keywords: Genome rearrangement; Sorting by reversals; Gene adjacency; Maximum matching; Alternating cycle (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0346-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:4:d:10.1007_s10878-018-0346-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0346-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().