TY - JOUR
T1 - An approximation algorithm for genome sorting by reversals to recover all adjacencies
AU - Zhai, Shanshan
AU - Zhang, Peng
AU - Zhu, Daming
AU - Tong, Weitian
AU - Xu, Yao
AU - Lin, Guohui
N1 - Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2019/5/1
Y1 - 2019/5/1
N2 - 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.
AB - 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.
KW - Alternating cycle
KW - Gene adjacency
KW - Genome rearrangement
KW - Maximum matching
KW - Sorting by reversals
UR - http://www.scopus.com/inward/record.url?scp=85053379661&partnerID=8YFLogxK
U2 - 10.1007/s10878-018-0346-y
DO - 10.1007/s10878-018-0346-y
M3 - Article
AN - SCOPUS:85053379661
SN - 1382-6905
VL - 37
SP - 1170
EP - 1190
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 4
ER -