有向基因组间重组距离的线性时间计算

讨论基于基因组中染色体之间的移位、染色体内部的翻转、融合和分裂的基因组排序问题,给出了计算两个有向多重基因组重组距离的线性时间算法.     

图的L(dm,1n)-标号

将图的L(d，1)．标号问题推广到L(d^m-，1^n-)-标号，并将其转化成该图的m-方图的L(d，1^n-)-标号．给出了求一般简单图的L(d，1^n-)-标号的两种算法．     

禾本科同源染色体对趋同进化的比较基因组学

多个禾本科物种全基因组测序的相继完成为禾本科植物基因组物理和遗传结构进化历史的研究提供了前所未有的良好机遇。以五个禾本科物种为研究对象,利用基因同源共线性方法对其基因组进行了比对分析,获得了物种的同源信息,并根据同源信息结合基因组同源结构分析,确定了物种基因组内和基因组间的同源染色体片段。比较分析同源染色体对上重复DNA片段之间的分子距离,初步揭示了禾本科植物同源染色体对间趋同进化规律,研究结果有助于理解染色体结构受非正常遗传重组影响的进化机制。     

移位变换下一类进化树的重构问题

讨论多重基因组在移位变换下的一类进化树的重构问题：给定一个由若干基因组组成的集族∏与另一个基因组A，其中所有基因组由同样的一些有向的基因组成，且每个基因组由相同数目的染色体组成，每一个基因在每个基因组中恰好出现一次，所有基因组有相同的尾基因集合，要求构造一个由A到∏的进化树，使得沿此树所发生的移位变换数目最少．给出由一个基因组生成一些给定基因组的近似算法；在一个特殊情况下给出其多项式时间算法．     

无向反转排序问题的遗传模拟退火求解

在推断两个基因组的进化关系上反转排序是一个重要问题.无向排列排序问题已被证明是一个NP-困难问题,目前,最好的算法是3/2-近似算法.基于一个无向排列π的反转距离等于由π所生成的包含2n个有向排列集Sign(π)中最优排列的反转距离,给出应用遗传模拟退火算法计算基因组重排的反转距离的方法.实验结果显示,这个方法优于3/2-近似算法.     

无向反转排序问题的遗传模拟退火求解

在推断两个基因组的进化关系上反转排序是一个重要问题。无向排列排序问题已被证明是一个NP-困难问题,目前,最好的算法是3/2-近似算法。基于一个无向排列π的反转距离等于由π所生成的包含2n个有向排列集Sign(π)中最优排列的反转距离,给出应用遗传模拟退火算法计算基因组重排的反转距离的方法。实验结果显示,这个方法优于3/2-近似算法。     

基于翻转和删除形式的染色体完美重组

研究了基于翻转和删除形式的染色体完美重组问题,并给出了多项式算法。     

不同进化历程下的异源四倍体小麦核型进化及其稳定性分析

以人工新合成、野生天然及栽培异源四倍体小麦为实验材料模拟四倍体小麦形成初期、自然进化及人工驯化等阶段，利用荧光原位杂交技术(FISH)对各群体进行核型的鉴定和比较分析.结果表明：新合成群体存在亚基因组间序列重组，重组位置主要集中在染色体长臂端部；野生天然群体积累了大量的序列重组，除3号同源群外，其他同源群均出现了近着丝粒区的片段渗入；栽培群体仍有新的重组现象出现，但与自然进化过程相比明显减少.各群体内的核型检测结果表明，人工新合成群体存在少量的染色体结构变化，野生天然和栽培群体则趋于稳定.本研究结果为明确多倍体作物在进化过程中的核型变化规律，了解其核型稳定程度提供重要的理论依据.     

NIQGA改进及基于可变角距离的新型量子进化算法

为了提高量子进化算法的执行效率,在NIQGA算法基础上,通过改进△θi和S(αi,βi)参数表提出了一种改进算法INIQGA.又通过引入量子比特间角距离定义,提出了一种基于可变角距离旋转的量子进化算法QEA-VAR,该算法采用旋转门操作进行种群进化时,依据当前染色体中量子比特|φ〉i与最优解对应基态| 0〉或| 1〉的...     

利用基因重组策略改进遗传算法

为了克服标准遗传算法的早熟现象，提高遗传算法的全局收敛性，提出了一种基于基因重组策略的遗传算法。该算法定义了一种新的交叉算子，即移位逻辑交叉算子(包括蝶形移位交叉算子和洗牌移位交叉算子)，用它们对染色体的部分基因实现有规律的交叉重组。实验结果表明，该算法比经典的遗传算法具有更好的收敛性和稳定性。     

基于基因次序的基因组问距离的计算

给出了计算两个具有相同内容、不同次序的基因组之间距离的算法.给定一组内容相同、次序不同的基因组,构造一个完全图,寻找一个基因组使得它与给定的各个基因组之间距离的累加和达到最小,这个问题可以转化为偈P问题.利用最小生成树方法找到一个中心基因组,接下来构造断点图,最后利用断点图来计算集合中的每一个基因组和中心基因组之间的距离.     

Engineering evolution to study speciation in yeasts

The Saccharomyces 'sensu stricto' yeasts are a group of species that will mate with one another, but interspecific pairings produce sterile hybrids. A retrospective analysis of their genomes revealed that translocations between the chromosomes of these species do not correlate with the group's sequence-based phylogeny (that is, translocations do not drive the process of speciation). However, that analysis was unable to infer what contribution such rearrangements make to reproductive isolation between these organisms. Here, we report experiments that take an interventionist, rather than a retrospective approach to studying speciation, by reconfiguring the Saccharomyces cerevisiae genome so that it is collinear with that of Saccharomyces mikatae. We demonstrate that this imposed genomic collinearity allows the generation of interspecific hybrids that produce a large proportion of spores that are viable, but extensively aneuploid. We obtained similar results in crosses between wild-type S. cerevisiae and the naturally collinear species Saccharomyces paradoxus, but not with non-collinear crosses. This controlled comparison of the effect of chromosomal translocation on species barriers suggests a mechanism for the generation of redundancy in the S. cerevisiae genome.     

基于图的情境离群点检测方法

针对异常模式挖掘中的情境离群点检测问题,提出一种基于图的检测方法.首先对数据实例构建一个实例图,然后采用一个滑动窗口穿越数据实例,对处于滑动窗口内的数据实例,计算结点之间的闵可夫斯基距离作为边权值,然后采用最小生成树聚类算法对实例图进行聚类,再采用第二个滑动窗口穿越数据实例,根据窗口内的数据实例是否属于主趋势聚类赋予不同的离群值评分,不属于主趋势聚类的数据实例被认为是潜在的离群点.仿真实验和实际数据分析表明该方法在一元序列数据检测中是切实可行的,该方法具有较好的适用性和扩展性.     

Human subtelomeres are hot spots of interchromosomal recombination and segmental duplication

Human subtelomeres are polymorphic patchworks of interchromosomal segmental duplications at the ends of chromosomes. Here we provide evidence that these patchworks arose recently through repeated translocations between chromosome ends. We assess the relative contribution of the principal mechanisms of ectopic DNA repair to the formation of subtelomeric duplications and find that non-homologous end-joining predominates. Once subtelomeric duplications arise, they are prone to homology-based sequence transfers as shown by the incongruent phylogenetic relationships of neighbouring sections. Interchromosomal recombination of subtelomeres is a potent force for recent change. Cytogenetic and sequence analyses reveal that pieces of the subtelomeric patchwork have changed location and copy number with unprecedented frequency during primate evolution. Half of the known subtelomeric sequence has formed recently, through human-specific sequence transfers and duplications. Subtelomeric dynamics result in a gene duplication rate significantly higher than the genome average and could have both advantageous and pathological consequences in human biology. More generally, our analyses suggest an evolutionary cycle between segmental polymorphisms and genome rearrangements.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

Chromosomal evolution in Saccharomyces

The chromosomal speciation model invokes chromosomal rearrangements as the primary cause of reproductive isolation. In a heterozygous carrier, chromosomes bearing reciprocal translocations mis-segregate at meiosis, resulting in reduced fertility or complete sterility. Thus, chromosomal rearrangements act as a post-zygotic isolating mechanism. Reproductive isolation in yeast is due to post-zygotic barriers, as many species mate successfully but the hybrids are sterile. Reciprocal translocations are thought to be the main form of large-scale rearrangement since the hypothesized duplication of the whole yeast genome 10(8) years ago. To test the chromosomal speciation model in yeast, we have characterized chromosomal translocations among the genomes of six closely related species in the Saccharomyces 'sensu stricto' complex. Here we show that rearrangements have occurred between closely related species, whereas more distant ones have colinear genomes. Thus, chromosomal rearrangements are not a prerequisite for speciation in yeast and the rate of formation of translocations is not constant. These rearrangements appear to result from ectopic recombination between Ty elements or other repeated sequences.     

用模拟退火算法求解无向排列的反转排序问题

分子生物学中基因元方向的反转基因组重排问题在数学上已被证明是一个NP-难问题。目前，较好的算法是Christie(2001)的3／2-近似算法，本文给出一种适合于计算基因元方向的反转基因组重排问题的模拟退火算法，定义了解的邻域结构，数据实验的结果表明该算法性能优于3／2-近似算法。     

基于免疫算法的无向排列的反转排序问题

提出一种基于免疫算法的无向排列的反转排序的方法，将一种免疫算子加入到遗传算法的框架中，通过对个体接种疫苗来进一步提升个体的存活能力。数据实验的结果表明，该算法性能优于Christe提出的3/2-近似算法。