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

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

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

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

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

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

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

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

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

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

含有反转、删除或插入操作的部分排序基因组重组

Zheng等给出了一个只含有反转操作的部分排序基因组重组的算法.本文推广了这一结果,给出了允许有删除或插入操作的两个含有不同基因集合的部分排序基因组重组的算法.     

装箱问题的一种新的近似算法

 研究了一维装箱问题(Bin Packing Problem),给出了一个新的近似算法:交叉装填算法(简称CF算法).证明了CF算法达到装箱问题的最好的近似值3/2;并且当这些物件的大小按非增性质预先排序后,CF算法的时间复杂度是线性的.     

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

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

柞蚕微孢子虫基因组LTR反转座子鉴定与进化分析

【目的】鉴定柞蚕微孢子虫(Nosema pernyi)基因组中LTR反转座子的种类、数量和遗传关系。【方法】从GenBank数据库下载柞蚕微孢子虫基因组序列,采用MGEScan软件筛选潜在重复元件,通过NCBI-BLAST与不同物种的逆转酶进行比对,含有逆转录酶结构域的序列认定为LTR反转座子,并探讨它们的结构特征、所属类型和基因组分布特点。【结果】从柞蚕微孢子虫基因组中共发现6个LTR反转座子家族即Nar1,Nar2,Nar3,Nar4,Nar5和Nar6,长度在3～4kb之间;大部分家族有相似的LTR末端核苷酸,但靶位点重复和拷贝数存在差异;逆转录酶结构域系统进化树显示6个LTR反转座子家族均属于Ty3/Gypsy类型,且与家蚕微孢子虫(Nosema bombycis)LTR反转座子形成姊妹分支;Nar2和Nar4家族在基因组上成串排列,具有相似的分布特征。【结论】柞蚕微孢子虫基因组中存在Ty3/Gypsy类型的LTR反转座元件,进化地位与家蚕微孢子虫最为接近;LTR反转座子家族重复元件在基因组上成串排列,可能是柞蚕微孢子虫基因组扩张的潜在因素之一。     

带背包约束的基数公平分配问题

研究了带背包约束的基数公平分配问题,即将给定的n个物品放入m个背包,在不超过背包容量的情况下,使得背包中装入的最小物品数尽可能大.通过预处理,可以假定每一个实例的最优值为k且h=km.得到如下的结果:①当所有背包的容量均相同时,通过对3-划分问题的归约证明了该问题不存在近似比大于2/3的近似算法,并基于贪婪法给出一个目标函数至少为k-1的近似算法;②当背包的容量不等时,通过对,维数值匹配问题的归约证明了该问题不存在近似比大于1/2的近似算法,并基于线性规划取整算法给出一个目标函数至少为k-2的近似算法.