IEEE/ACM Trans Comput Biol Bioinform. 2021 Nov-Dec;18(6):2870-2876. doi: 10.1109/TCBB.2020.2993002. Epub 2021 Dec 8.
Genome rearrangements are mutations affecting large portions of a genome, and a reversal is one of the most studied genome rearrangements in the literature through the Sorting by Reversals (SbR) problem. SbR is solvable in polynomial time on signed permutations (i.e., the gene orientation is known), and it is NP-hard on unsigned permutations. This problem (and many others considering genome rearrangements) models genome as a list of its genes in the order they appear, ignoring all other information present in the genome. Recent works claimed that the incorporation of the size of intergenic regions, i.e., sequences of nucleotides between genes, may result in better estimators for the real distance between genomes. Here we introduce the Sorting Signed Permutations by Intergenic Reversals problem, that sorts a signed permutation using reversals both on gene order and intergenic sizes. We show that this problem is NP-hard by a reduction from the 3-partition problem. Then, we propose a 2-approximation algorithm for it. Finally, we also incorporate intergenic indels (i.e., insertions or deletions of intergenic regions) to overcome a limitation of sorting by conservative events (such as reversals) and propose two approximation algorithms.
基因组重排是影响基因组大片段的突变，而倒位是文献中通过反转排序（Sorting by Reversals，SbR）问题研究最多的基因组重排之一。对于有符号排列（即基因方向已知），SbR 问题可以在多项式时间内解决，而对于无符号排列则是 NP 难问题。这个问题（以及许多考虑基因组重排的其他问题）将基因组建模为其基因按出现顺序的列表，忽略基因组中存在的所有其他信息。最近的研究声称，整合基因间区的大小，即基因之间的核苷酸序列，可能会为真实的基因组之间的距离提供更好的估计值。在这里，我们引入了通过基因间倒位排序有符号排列的问题，该问题使用基因顺序和基因间大小上的倒位来对有符号排列进行排序。我们通过从 3 部分划分问题的归约证明了这个问题是 NP 难的。然后，我们为它提出了一个 2-近似算法。最后，我们还整合了基因间插入缺失（即基因间区的插入或缺失），以克服基于保守事件（如倒位）排序的局限性，并提出了两种近似算法。
