Bérard Sèverine, Bergeron Anne, Chauve Cedric, Paul Christophe
Département de Mathématiques et d'Informatique Appliquées, INRA Toulouse, Castanet-Tolosan, France.
IEEE/ACM Trans Comput Biol Bioinform. 2007 Jan-Mar;4(1):4-16. doi: 10.1109/TCBB.2007.1011.
We propose new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals. We describe a combinatorial framework for this problem that allows us to characterize classes of signed permutations for which one can compute, in polynomial time, a shortest reversal scenario that conserves all common intervals. In particular, we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse, and rat.
我们提出了用于计算成对重排情形的新算法，这些算法能保留基因组的组合结构。更确切地说，我们研究了在不破坏公共区间的情况下通过反转来对有符号排列进行排序的问题。我们描述了针对此问题的一个组合框架，该框架使我们能够刻画有符号排列的类别，对于这些类别，可以在多项式时间内计算出一个最短的反转情形，该情形能保留所有公共区间。特别地，我们定义了一类排列，对于这类排列，可以使用一种非常简单的算法在线性时间内完成此计算，该算法不依赖于用于通过反转进行排序的经典汉内哈利 - 佩夫兹纳理论。我们将这些方法应用于计算从人类、小鼠和大鼠X染色体的16个同线基因块得到的排列之间的重排情形。
