Bergeron Anne, Medvedev Paul, Stoye Jens
Départment d'informatique, Université du Québec à Montréal, Montreal, QC, Canada.
J Comput Biol. 2010 Sep;17(9):1213-25. doi: 10.1089/cmb.2010.0091.
There have been many widely used genome rearrangement models, such as reversals, Hannenhalli-Pevzner (HP), and double-cut and join. Though each one can be precisely defined, the general notion of a model remains undefined. In this paper, we give a formal set-theoretic definition, which allows us to investigate and prove relationships between distances under various existing and new models. Among our results is that sorting in the HP model is equivalent to sorting in the reversal model when the initial and final genomes are linear uni-chromosomal. We also initiate the formal study of single-cut operations by giving a linear time algorithm for the distance problem under a new single-cut and join model.
已经有许多被广泛使用的基因组重排模型，例如反转、汉内哈里 - 佩夫兹纳（HP）模型以及双切割与连接模型。尽管每个模型都能被精确地定义，但模型的一般概念仍然未被定义。在本文中，我们给出了一个形式化的集合论定义，这使我们能够研究并证明各种现有模型和新模型下距离之间的关系。我们的成果包括，当初始基因组和最终基因组都是线性单染色体时，HP模型中的排序等同于反转模型中的排序。我们还通过给出一个关于新的单切割与连接模型下距离问题的线性时间算法，开启了对单切割操作的形式化研究。
