武汉科技大学数学建模竞赛研究生组赛题.DOC

武汉科技大学数学建模竞赛研究生组赛题 A题 基因重排 进化理论是系统生物学研究的一个主要分支, 它主要研究种群的进化过程, 以及各现代物种之间的亲疏关系。1980年代以前，生物学家一般采用的研究方法[1]是先分别比较不同物种基因的差异，即核苷酸(A,C,T,G)序列的差异, 然后将这些差异汇总来决定物种关系的远近。而1980年代末生物学家发现[2]，在一些种群中不同物种的基因内部核苷酸序列差异很小，但是这些基因在各自物种的染色体上的位置差异较大。这一发现表明进化理论的传统研究方法对有些种群并不适用，需要将基因在染色体上的位置这一因素考虑进去，并占主导地位。另外，研究表明进化过程中基因在染色体位置的变化既可以是单个基因的变化，也可以是一段连续基因的整体位置的变化，称为进化事件。一个基因在染色体上的排列方式可以通过各种进化事件变成另外一个排列方式，所需的最少次数称为最小转换次数，它可以用来衡量两个不同物种的亲疏。 (1) “换位”是被生物学家所广泛承认的进化事件之一。它是这样发生的，某一串相邻的基因从原有位置整体移动到某两个相邻基因之间。比如我们用字母来表示基因， 把他们排成一排表示在染色体上的位置，那ACDEBGF到 ABGCDEF就发生了一次“换位”，因为CDE整体插入到G和F之间。假设某两个物种基因在染色体上的排列分别为和，并且在进化过程中只发生了换位事件，试给出算法计算这两物种之间至少发生了多少次换位？ (2) 除了一些菌类以外，大多数物种的染色体是线型的，因此都有方向，他们上面的基因也有方向。“倒置”是生物学家所发现的又一个进化事件。它是指一整串相邻的基因倒置。例如，我们用字母来表示基因，用正负号来表示基因的方向。那么 A -C B -F E D到 A F -B C E D 就发生了一次倒置。因为-C B -F 变换成了 F -B C。 例如：到三步可以完成(下划线是倒置的基因组) ( ( ( 试给出算法来计算下面两个物种之间所需倒置的次数。 (3) 实际上，基因是会在同一染色体上重复出现的。建立模型，假设基因变换仅限于换位、倒置和复制，给出一个算法评价不同染色体代表的生物的亲疏关系，并对如下例子计算结果。 例 [1] R.F. Doolittle, M.W. Hunkapiller, L.E. Hood, S.G. Devare, K.C. Robbins, S.A. Aaronson, and H.N. Antoniades. Simian sarcoma virus onc gene, v-sis, is derived from the gene (or genes) encoding a platelet-derived growth factor. Science, 221(1983), 275--277 [2] J.D. Palmer and L.A. Herbon. Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. Journal of Molecular Evolution, 27(1988), 87--97