一种新的关联特征和模糊聚类的进化树构建方法*

利用三联体和单联核苷酸的联合概率分布的差异来表示序列之间的差异,提出了一种新的关联特征TBC;对TBC特征矩阵进行平移极差变换,利用指数切比雪夫距离法构建了模糊相似矩阵,采用模糊聚类中的传递闭包法构建进化树。该方法不需要多序列比对,计算简单。对两组基因组序列构建进化树,实验结果验证了该方法的有效性。     

用DTW算法构建细胞色素c的进化树

构建生物的细胞色素c的进化树对蛋白质一级结构的种属差异的研究十分重要.本文通过一维映射,将蛋白质一级序列转化为时间序列,采用DTW算法来计算2个时间序列之间的DTW距离,用以量度序列之间的相似度,给出比较蛋白质序列相似性的度最新算法,用以分析不同物种的细胞色素c蛋白一级序列的相似性,构建序列进化树,得到较好的结果.本方法较其它方法简单快速,为研究生物序列进化关系提供新的手段.     

基于平均交互信息量的DNA序列相似性分析

序列相似性分析是生物信息学中一个重要问题,对于研究物种的进化起源有着重要的意义.序列相似性算法包括基于序列比对的方法及非比对方法两种.基于比对的方法对于序列整体的衡量略有欠缺;非比对算法中有DNA曲线化方法以及比较序列各自整体碱基分布间的信息量差异的方法,只是考虑了序列整体信息间的差异,但未考虑序列各个位点间的差异.因此,提出了一种基于信息熵的相似性度量模型,把序列比对与信息量差异结合起来,将两条比对后的序列间的平均交互信息量与其联合熵之比作为两条序列的相似性度量.使用该度量构建了11个物种的相似性矩阵,对各物种间的相似性进行了分析,结果在一定程度上与生物分类学相契合.通过距离矩阵所构建的进化树,也反映了各物种间的进化关系,表明该模型的设计具有合理性.     

基于两层隐马尔可夫模型的入侵检测方法*

在基于系统调用的入侵检测研究中,如何提取系统调用序列模式是一个重要问题.提出一种利用进程堆栈中的函数返回地址链信息来提取不定长模式的方法.同王福宏的不定长模式提取方法相比,该方法可以取得更完备的模式集.在此基础上,基于系统调用序列及其对应的不定长模式序列构建了一个两层隐马尔可夫模型来检测异常行为,与仅利用系统调用序列信息的经典隐马尔可夫方法相比,该方法可以取得更低的误报率和漏报率.     

A New Correct Method of DNA Sequence Genetic Distance

进化树是推演生命历史的一个重要工具.在构建进化树的所有算法中,基于进化距离的算法是其中研究的重点.但是,这一方法较为严重地依赖着距离矩阵的质量.人们开发了多种基于生物事实的进化模型来改进距离矩阵的构建过程,很大程度上提高了进化距离的准确性.同时,也提出了许多方法来检测距离矩阵的质量.文中提出了基于模型的距离以及p距离,采用一种组合的新距离的方式来构建距离矩阵.同时采用直接检测距离矩阵的统计学计分方法以及构建进化树,对比实验结果表明文中的方法实用且有效.     

一种基于Quartet Puzzling和邻接法的进化树构建算法

最大似然法是目前较准确的一种进化树构建方法,但是其时间复杂度非常高.在实际应用中,用分治策略实现最大似然法的Quartet Puzzling(QP)得到了人们的关注.它首先估计Quartet拓扑结构集合Q,然后利用重组技术将Q中的信息合并到一起构成一个包含所有序列的进化树.研究表明,QP的准确性不像人们所期望的那样高.如何快速有效地将Q所包含的信息融合在一起仍然是QP所面-临的一个问题.为了提高QP,结合邻接法提出一种新的进化树构建方法QPNJ.理论上,QPNJ与QP具有相同的时间复杂度.通过模拟实验将QPNJ与QP以及目前流行的进化树构建方法进行了比较.结果表明,QPNJ比QP和邻接法更准确,并且其性能不依赖于模型树的结构,从而证明了QPNJ的有效性.     

基于模式匹配的多序列相似性分析

本文提出了一种基于模式匹配的多序列相似性分析方法，该方法将模式匹配应用到序列比对中，采用Kimura双参数模型计算进化矩阵并构造物种进化树，进行相似性分析。实验结果表明该方法的有效性。     

基于粗粒化的流感病毒蛋白进化树构建*

在127065条血凝素、神经氨酸酶流感病毒蛋白基础上,提出基于粗粒化的病毒蛋白进化树的构建方法.首先基于病毒蛋白序列特征,给出序列间相似性度量,提取流感病毒系统层次递阶结构,并定义层次聚类指标,确定最佳聚类数.然后基于距离中心最近的原则提取流感病毒系统代表.最后采用距离度量构造流感病毒进化树.实验表明,相同流感病毒具有宿主相同、时间跨度较小、爆发地点相近,更倾向于处于相同分支的特点,这与已有的文献吻合,因此该方法有利于挖掘病毒变异轨迹.     

标签传播时间序列聚类的股指期货套期保值策略研究

利用时间序列聚类方法进行股指期货的套期保值,关键要选择合适的聚类方法。本文从新的视角来研究并提高时间序列聚类方法在金融数据分析领域的应用性能,提出一种基于标签传播时间序列聚类的股指期货套期保值模型。该模型以动态时间弯曲为相似性度量方法来构建现货股票网络空间结构,将每只股票看作一个节点,利用标签传播方法将节点划分到不同的簇中,最终实现股票数据聚类。另外,构建最小追踪误差优化模型来确定每支股票在现货组合中的最优权重,从而得到最优组合。实验分别比较新方法和传统聚类方法确定现货组合的追踪误差,结果表明新方法能够提高现货组合的追踪精度,为丰富金融市场投资和管理方式提供新的研究思路。     

一种基于NJ的高效构建系统进化树算法

在分析和证明了构建进化树的Neighbor-joining算法存在的不足后,提出了一种新的改进算法。算法主要有以下两点改进采用Kimura两参数模型,根据此模型来计算DNA序列距离,并且定义了新的校正距离。计算机模拟结果表明,改进算法的效率明显地优于NJ算法。     

基于遍历序列的唯一确定树或二叉树的方法

基于遍历序列的唯一确定树或二叉树的方法既体现了树或二叉村的遍历序列的部分性质,又是建立树或二叉村的存储结构的主要依据,本文首先介绍了由一棵二叉树的某两种遍历序列或某种遍历序列和结点的某种信息可以唯一确定该二叉树的各种可能方法,然后分别针对树、严格二叉树与雨季叉排序树加以介绍,本文比较全面的介绍了基于遍历离列的唯一确定树或二叉树的方法,进一步完善了树或二叉树的遍历序列的性质。     

Clustering based distributed phylogenetic tree construction

Phylogenetic tree construction has received much attention recently due to the availability of vast biological data. In this study, we provide a three step method to build phylogenetic trees. Firstly, a density-based clustering algorithm is used to provide clusters of the population at hand using the distance matrix which shows the distances of the species. Secondly, a phylogenetic tree for each cluster is constructed by using the neighbor-joining (NJ) algorithm and finally, the roots of the small phylogenetic trees are connected again by the NJ algorithm to form one large phylogenetic tree. To our knowledge, this is the first method for building phylogenetic trees that uses clustering prior to forming the tree. As such, it provides independent phylogenetic tree formation within each cluster as the second step, hence is suitable for parallel/distributed processing, enabling fast processing of very large biological data sets.The proposed method, clustered neighbor-joining (CNJ) is applied to 145 samples from the Y-DNA Haplogroup G. Distances between male samples are the variation in their set of Y-chromosomal short tandem repeat (STR) values. We show that the clustering method we use is superior to other clustering methods as applied to Y-DNA data and also independent, fast distributed construction of phylogenetic trees is possible with this method.     

Approximation algorithms for tree alignment with a given phylogeny

We study the following fundamental problem in computational molecular biology: Given a set of DNA sequences representing some species and a phylogenetic tree depicting the ancestral relationship among these species, compute an optimal alignment of the sequences by the means of constructing a minimum-cost evolutionary tree. The problem is an important variant of multiple sequence alignment, and is widely known astree alignment. We design an efficient approximation algorithm with performance ratio 2 for tree alignment. The algorithm is then extended to a polynomial-time approximation scheme. The construction actually works for Steiner trees in any metric space, and thus implies a polynomial-time approximation scheme for planar Steiner trees under a given topology (with any constant degree). To our knowledge, this is the first polynomial-time approximation scheme in the fields of computational biology and Steiner trees. The approximation algorithms may be useful in evolutionary genetics practice as they can provide a good initial alignment for the iterative method in [23].Supported in part by NSERC Operating Grant OGP0046613.Supported in part by NSERC Operating Grant OGP0046613 and a Canadian Genome Analysis and Technology Research Grant.Supported in part by US Department of Energy Grant DE-FG03-90ER6099.     

综合故障树分析方法在容错计算机系统中的应用

该文运用二元决策图（Binary Decision Diagram）分析传统的静态故障树，运用Markov链分析新兴的动态故障树，由此形成一种创新性的故障诊断方法：综合故障树（Integrated Fault Tree）分析法。综合故障树分析法运用分而治之的策略处理各种故障，不仅加深了故障诊断、分析的精度，同时也拓展了故障树分析法的运用领域。该文结合实例，运用综合故障树分析法解决容错计算机系统中动态时序特性的建模困难问题；分析结果表明，在容错计算机系统中运用此方法，可以有效地对系统建模和分析系统可靠性。     

一种新的故障树定性分析方法

提出基于割序集的分析方法以研究故障树顶事件发生时基本事件的动态行为。利用顺序失效符表示事件的顺序失效关系,并将静态门和动态门转化为顺序失效表达式来描述故障树中各种门的动态行为,利用顺序失效表达式构建故障树的割序集。结合实例阐述故障树割序集生成算法的流程。该算法将失效行为表示为长度小于系统中部件个数的有序部件序列,为研究故障树提供了一种新的定性分析方法。     

层次结构树木物理运动的实时仿真

提出一种在GPU上实现基于力学运动原理的层次结构树木运动的并行仿真技术。该技术通过分析物理运动原理与多层次的矩阵结构(HMSM)算法的并行性,来达到将树木动画在图形硬件CUDA平台上进行加速的目的。首先介绍层次结构树木在外力诸如风力等作用下的物理运动原理;然后,针对树木的物理运动以及层次结构叠加算法详细地进行并行性分析;之后着重阐述CUDA框架下树木运动的并行结构设计过程与并行算法的详细设计方法;最后在GPU上执行树木物理运动仿真。实验结果表明,该技术不但能够生成真实感较强的树木动画序列,还能够实时模拟基于物理的树木运动。同时,该技术给计算机动画的加速算法提供了很好的思想。     

树木结构层次细化的立体树木图像构建

目的 2维转3维技术可以将现有的丰富2维图像资源快速有效地转为立体图像,但是现有方法只能对树木的整体进行深度估计,所生成的图像无法表现出树木的立体结构。为此,提出一种树木结构层次细化的立体树木图像构建方法。方法 首先利用Lab颜色模型下的像素色差区别将2维树木图像的树干区域和树冠区域分割开来,并对树冠区域进行再分割;然后,在深度梯度假设思想基础上建立多种类型的深度模板,结合深度模板和树冠的区域信息为典型树木对象构建初始深度图,并通过基础深度梯度图组合的方式为非典型树木进行个性化深度构建;最后,根据应用场景对树木深度信息进行自适应调整与优化,将树木图像合成到背景图像中,并构建立体图像。结果 对5组不同的树木图像及背景图像进行了立体树木图像的构建与合成。结果表明,不同形态的树木图像都能生成具有层次感的深度图并自适应地合成到立体背景图像中,构建树木图像深度图的时间与原始树木图像的尺寸成正比,而构建立体树木图像并合成到背景中所需时间在24 s之间。对立体图像质量的主观评价测试中,这些图像的评分均达到良好级别以上,部分立体图像达到了优秀级别。结论 该方法充分利用了树木的形态结构特征,能同时适用于典型和非典型树木,所构建的立体树木图像质量较高,具有丰富的层次感,并具有舒适的立体观看效果。     

An Edit Distance between Quotiented Trees

Abstract. In this paper we propose a dynamic programming algorithm to compare two quotiented trees using a constrained edit distance. A quotiented tree is a tree defined with an additional equivalent relation on vertices and such that the quotient graph is also a tree. The core of the method relies on an adaptation of an algorithm recently proposed by Zhang for comparing unordered rooted trees. This method is currently being used in plant architecture modelling to quantify different types of variability between plants represented by quotiented trees.     

个性化编辑的轻量化3维树木模型构建

目的 3维树木几何结构和拓扑结构的复杂性,不仅使得真实感3维树木模型的构建过程十分复杂,而且构建的模型文件包含大量的几何数据。针对3维树木模型的构建过程复杂和模型数据量大的问题,提出一种支持骨架个性化编辑的轻量化3维树木模型构建方法。方法 该方法在提取树木模型骨架结构的基础上,通过交互方式对3维树木模型的骨架进行个性化编辑以生成3维树木模型的全新骨架结构,并采用枝干和树冠模型的简化方法实现轻量化3维树木模型的构建。结果 该方法不仅能快速创建轻量化的3维树木模型,减少3维树木可视化时的模型绘制时间;而且能通过骨架个性化编辑来设计树木的拓扑结构,有助于增加同一品种树木外部表现形态的多样性。结论 通过应用表明,本文轻量化3维树木模型构建方法不仅可以构建具有不同表现形态的3维树木模型,而且简化后的3维树木模型可以在无线网络、移动终端等资源有限情况下进行3维树木可视化。     

基于树编辑距离的工作流距离度量方法

在工作流的发现和聚类等应用中,需要对两个工作流模型的距离进行度量。因此,提出一种计算两个不同结构化工作流的距离定量度量方法。首先介绍了结构化工作流,并将每一个结构化工作流转换为流程结构树;然后基于两个结构树之间的树编辑距离来计算工作流之间的距离及相应相似度。该距离度量方法满足距离度量的3个属性,即同实体不可区分性、对称性和三角不等式性质。这些属性使得该距离度量方法可以在工作流模型管理活动中作为定量分析工具。实验结果表明,基于树编辑距离的工作流度量方法是可行的。同时,与基于邻接矩阵的距离度量方法相比,该方法考虑了不同结构之间的语义距离,有效验证了此方法的合理性。