Bergeron Anne, Stoye Jens
CGL, Université du Québec à Montréal, Montreal, Canada.
J Comput Biol. 2006 Sep;13(7):1340-54. doi: 10.1089/cmb.2006.13.1340.
The comparison of genomes with the same gene content relies on our ability to compare permutations, either by measuring how much they differ, or by measuring how much they are alike. With the notable exception of the breakpoint distance, which is based on the concept of conserved adjacencies, measures of distance do not generalize easily to sets of more than two permutations. In this paper, we present a basic unifying notion, conserved intervals, as a powerful generalization of adjacencies, and as a key feature of genome rearrangement theories. We also show that sets of conserved intervals have elegant nesting and chaining properties that allow the development of compact graphic representations, and linear time algorithms to manipulate them.
对具有相同基因内容的基因组进行比较，依赖于我们比较排列的能力，这可以通过测量它们的差异程度，或者测量它们的相似程度来实现。除了基于保守邻接概念的断点距离这一显著例外，距离度量并不容易推广到多于两个排列的集合。在本文中，我们提出了一个基本的统一概念——保守区间，它是邻接关系的有力推广，也是基因组重排理论的关键特征。我们还表明，保守区间集具有优雅的嵌套和链式属性，这使得可以开发紧凑的图形表示以及用于操作它们的线性时间算法。
