An approximation algorithm for genome sorting by reversals to recover all adjacencies
An approximation algorithm for genome sorting by reversals to recover all adjacencies
复制标题
通过反转恢复所有邻接的基因组排序的近似算法
DOI：
10.1007/s10878-018-0346-y
复制
发表时间：
2019
影响因子：
1
通讯作者：
Guohui Lin
中科院分区：
文献类型：
--
作者：
Shanshan Zhai;Peng Zhang;Daming Zhu;Weitian Tong;Yao Xu;Guohui Lin
基因组重排问题已经被广泛研究了二十多年，旨在了解基因组水平上的长距离基因突变的物种进化关系。虽然大多数早期研究都集中在忽略基因重复的简化基因组上，但数千个全基因组测序项目表明，一个基因组通常携带以各种方式沿基因组分布的多个基因重复。给定一个源基因组和一个目标基因组，其中一个是另一个中基因的重新排序，我们通过在源基因组上应用的最小逆转次数来测量进化距离，以恢复目标基因组中的所有基因邻接。我们定义这个优化问题，通过反转分类来恢复所有邻接，简称 SBR2RA。我们证明 SBR2RA 是 APX 难的，并揭示了与经典对应问题（反转排序问题）的一些相似之处和不同之处。从近似性的角度来看，我们提出了 a-近似算法，其中 是被怀疑为 NP 困难的相关优化问题的最佳近似率。
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 assorting by reversals to recover all adjacencies, orSBR2RAin short. We show thatSBR2RAis APX-hard and uncover some similarities and differences to the classic counterpart, thesorting by reversalsproblem. From the approximability perspective, we present a-approximation algorithm, whereis the best approximation ratio for a related optimization problem which is suspected to be NP-hard.