实例序列条数为常数9的翻转距离星树问题

讨论翻转距离星树问题,证明实例中有向符号序列个数为9时,翻转距离星树问题是NP-难解问题,并给出了一个该问题的多项式时间近似算法．     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

计算生物学中有关基因组翻转距离的NPC问题

1 基因组翻转距离问题的提出 20世纪80年代末,Jeffrey Palmer及其同事在对比甘蓝与芜箐甘蓝的基因序列时发现,排列形成两种基因序列的分子几乎完全相同,只是这些分子在两种基因中的排列顺序不一样。这一发现以及其后的研究表明,基因重组是生物演化过程中的一个基本特征。基因重组研究中多次遇到要用尽可能少的次数将一条基因序列中的片断翻转连接成新的基因的问题,这就是后来由D.Sankoff等提出的基因组翻转距离问题,或抽象为有向符号序列的翻转距离问题,D.Sankoff等猜测该问题是NP难解问题,然而他们没能给出证明。     

符号序列间的LZ复杂性距离及其应用

在符号序列LZ复杂性的计算原理上,提出了序列间条件LZ复杂性的概念.基于条件LZ复杂性,定义了一个非空序列间的LZ复杂性距离并证明了该距离满足距离测度的4个基本性质.将LZ复杂性距离应用于计算语言学和生物信息学的研究领域,选取20种自然语言文本和29种有胎盘哺乳动物的全线粒体基因组,将它们视为不同符号集上的符号序列,分别计算两类符号序列的LZ复杂性距离矩阵.基于LZ复杂性距离矩阵,重构了20种语言的语言关系树和29种哺乳动物的系统进化树.其结果符合它们真实的演化关系,说明了LZ复杂性距离定量刻画符号序列间差异的有效性.     

计算生物学中的9叶星树问题

本文讨论翻转距离星树问题,证明实例中有向符号序列个数为9时,翻转距离星树问题问题是NP-难解问题,并给出了一个该问题的多项式时间近似算法.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

点到任意多面体距离的快速计算方法

提出了一种快速计算空间点到任意多面体的有符号距离的方法,该方法以空间点为中心,采用动态搜索技术,能够快速准确地获得一个含多面体最近体元素在内的候选面片集,而且在一般情况下该候选集都足够小,从而对计算空间点到复杂多面体的最近距离起到明显的加速作用,与采用层次结构表示的方法相比,此方法避免了频繁计算点到各层次结构的距离,本算法可应用在需大量距离计算的环境,如距离场计算、虚拟环境下的碰撞检测,机器人运动规划及数据控加工过程的干涉检查等。     

隐私保护DNA序列汉明距离计算问题

DNA序列承载着人体重要的生物学信息,如何在保护隐私的情况下正确地对不同的DNA序列进行比对,成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度,在保护隐私的情况下,研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则,该规则将长度为n的DNA序列编码成长度为4n的0-1串,证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础,以GM加密算法为主要密码学工具,构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下,证明了协议的正确性,给出了基于模拟器的安全性证明,并对协议的效率进行了分析。     

时间序列的细微距离发现

时间序列是信息系统一储存在的一类重要数据对象,而序列间的距离计算是很多时间序列数据开采或数据提取问题的核心。针对目前的序列距离定义模型对非总体的细微关联特征不敏感的问题,提出了一种新的时间序列距离定义模－时间序列的细微距离ＭＤ（Ｘ,Ｙ）,并提出了一种将时间序列由时域映射到频域,在频域中分离出不同的序列变化形式,以确定时间序列细微差别程度的算法－ＦＤＤ算法。ＦＤＤ算法具有较高的效率,且可以 作基准值     

基因组一般移位排序问题的多项式时间算法

基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的,未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法,给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题,利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测.     

Lower Bounds on Learning Decision Lists and Trees

k-Decision lists and decision trees play important roles in learning theory as well as in practical learning systems.k-Decision lists generalize classes such as monomials,k-DNF, andk-CNF, and like these subclasses they are polynomially PAC-learnable [R. Rivest,Mach. Learning2(1987), 229–246]. This leaves open the question of whetherk-decision lists can be learned as efficiently ask-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [M. Anthony and N. Biggs, “Computational Learning Theory,” Cambridge Univ. Press, Cambridge, UK, 1992]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of 2^{logδ n}for anyδ<1, unlessNP⊂DTIME[2^{polylog n}]: a generalized set cover,k-decision lists,k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor ofn^δ, for some constantδ>0, unlessNP=P. Also,k-decision lists withl0–1 alternations cannot be approximated within a factor log^l nunlessNP⊂DTIME[n^{O(log log n)}] (providing an interesting comparison to the upper bound obtained by A. Dhagat and L. Hellerstein [in“FOCS '94,” pp. 64–74]).     

数值计算程序的存储复杂性分析

由于越来越多的技术用于缩小处理器与存储器之间的日益加大的速度差距,计算机的存储系统变得日趋复杂．现在,任何一个程序设计者,尤其是数值计算程序的设计者,若不考虑其所用计算平台存储系统的特点是很难获取高性能的．因此公用传统的算法评价方法,从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异,显然是不够的．计算平台存储系统的特点必须在分析算法的复杂性时加以考虑．孙家昶１９９     

An empirical investigation into the effects of chaos on different types of evolutionary crossover operators for efficient global search in complicated landscapes

In this study, a comprehensive empirical test is conducted to analyse the effects of two well-known chaotic maps, namely sinusoidal and logistic maps, on the efficacy of double Pareto crossover, Laplace crossover and simulated binary crossover operators for the global optimization of continuous problems. To do so, 13 well-known numerical benchmark problems in three distinctive dimensions, namely 50D, 100D and 200D, are considered and the genetic algorithm (GA) with simple version and chaos-enhanced versions of the mentioned crossover operators are utilized for optimizing these functions. Furthermore, a time complexity analysis is conducted to find out the impact of hybridizing the chaos and the evolutionary operators on the computational complexity of GA. The results of the experimental analysis provide us with fruitful information regarding the scalability, computational complexity and exploration/exploitation capability of the considered rival optimization algorithms, as well as, demonstrate the efficacy of chaos-evolutionary computing for numerical continuous optimizations.     

一种快速的基于占优树的多目标进化算法

为了解决多目标进化算法中适应值指派(fitness assignment)的耗时问题,提出了一种新颖的适应值指派方法--占优树.占优树保存了个体之间的必要信息,暗含了个体的密度信息,而且显著减少了个体之间的比较.此外,基于占优树的淘汰策略没有花费额外的代价就保存了种群多样性.在此基础上,提出了一种新的基于占优树的多目标进化算法.通过6个测试问题和3个方面的测试标准,新算法在接近真实的最优前沿和保持种群的多样性方面,与SPEA2和NSGA-II性能相当,但速度要比它们快得多.     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

统计遗传算法

本文讨论了遗传算法中框架定理的不足之处,并对之进行了改进,然后分析了遗传算法与Ａ算法的相似性,以及遗传算法的概率性质．由此联想到它与ＳＡ算法的相似性,在此基础上,作者将原先发展的一套ＳＡ算法的理论移植到遗传算法中来,建立一个新的算法,称之为统计遗传算法（简记为ＳＧＡ算法）．为适合于优化计算,作者引入最大值统计量及其对应的ＳＡ算法（简称为ＳＭＡ算法）,并将ＳＭＡ算法与ＧＡ算法相结合（记为ＳＧＡ（ＭＡＸ）算法）．新的算法不仅提高了算法的精度和降低了计算的复杂性,而且能克服ＧＡ算法中出现“早熟”的现象以及提供进行并行计算的可能性．更主要的是新的方法为ＧＡ算法的精度、可信度和计算复杂性的定量分析提供了理论和方法上的有力工具.