论文标题
通过前缀双切和加入对基因组进行分类
Sorting Genomes by Prefix Double-Cut-and-Joins
论文作者
论文摘要
在本文中，我们研究了通过签名和未签名的设置中前缀双切和加入（或DCJS）对单染色体线性基因组进行分类的问题。前缀DCJ削减了基因组和任何其他段的最左端段，并以两种可能的方式重组切断的端点：其中一种选择对应于前缀逆转，这将两种切割之间的元素顺序逆转（以及在签名的情况下以及它们的符号）。取决于我们仅考虑选项还是逆转，我们的主要结果是： （1）基于断点图的新结构下限，用于通过未签名的前缀逆转，未签名的前缀DCJ或签名的前缀DCJ进行排序； （2）用于通过符号前缀DCJ进行排序的多项式时间算法，从而在[8]中回答了一个空的问题； （3）通过未签名的前缀DCJ进行排序的3/2- approximation，据我们所知，这是{\ em前缀}重新排列问题的第一个分类问题，该问题严格地接受了近似值，严格小于2（明显的是多核溶解的问题除外）;最后， （4）一种用于通过基因组中的断点数量的无符号前缀DCJ进行排序的FPT算法。
In this paper, we study the problem of sorting unichromosomal linear genomes by prefix double-cut-and-joins (or DCJs) in both the signed and the unsigned settings. Prefix DCJs cut the leftmost segment of a genome and any other segment, and recombine the severed endpoints in one of two possible ways: one of these options corresponds to a prefix reversal, which reverses the order of elements between the two cuts (as well as their signs in the signed case). Depending on whether we consider both options or reversals only, our main results are: (1) new structural lower bounds based on the breakpoint graph for sorting by unsigned prefix reversals, unsigned prefix DCJs, or signed prefix DCJs; (2) a polynomial-time algorithm for sorting by signed prefix DCJs, thus answering an open question in [8]; (3) a 3/2-approximation for sorting by unsigned prefix DCJs, which is, to the best of our knowledge, the first sorting by {\em prefix} rearrangements problem that admits an approximation ratio strictly smaller than 2 (with the obvious exception of the polynomial-time solvable problems); and finally, (4) an FPT algorithm for sorting by unsigned prefix DCJs parameterised by the number of breakpoints in the genome.
