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

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

Comparing and aggregating partially resolved trees

Partially-resolved-that is, non-binary-trees arise frequently in the analysis of species evolution. Non-binary nodes, also called multifurcations, must be treated carefully, since they can be interpreted as reflecting either lack of information or actual evolutionary history. While several distance measures exist for comparing trees, none of them deal explicitly with this dichotomy. Here we introduce two kinds of distance measures between rooted and unrooted partially-resolved phylogenetic trees over the same set of species; the measures address multifurcations directly. For rooted trees, the measures are based on the topologies the input trees induce on triplets; that is, on three-element subsets of the set of species. For unrooted trees, the measures are based on quartets (four-element subsets). The first class of measures are parametric distances, where there is a parameter that weighs the difference between an unresolved triplet/quartet topology and a resolved one. The second class of measures are based on the Hausdorff distance, where each tree is viewed as a set of all possible ways in which the tree can be refined to eliminate unresolved nodes. We give efficient algorithms for computing parametric distances and give conditions under which Hausdorff distances can be calculated approximately in polynomial time. Additionally, we (i) derive the expected value of the parametric distance between two random trees, (ii) characterize the conditions under which parametric distances are near-metrics or metrics, (iii) study the computational and algorithmic properties of consensus tree methods based on the measures, and (iv) analyze the interrelationships among Hausdorff and parametric distances.     

基于四参数随机生长模型的页岩储层应力敏感分析

页岩储层的应力敏感性是影响其后期开发效果的关键因素,从微观的角度深入认识其应力敏感机理及其影响因素对页岩气的开发具有重要意义。借助四参数随机生长模型构建了不同孔隙度和不同孔隙大小分布的岩心样本,利用弹性力学理论模拟了不同有效应力作用下各个岩心孔隙半径的分布变化及其对岩心固有渗透率的影响,深入分析了孔隙大小及其形状因子与上述两者之间的关系。结果表明,导致页岩应力敏感的直接原因是有效应力作用下孔隙面积的减小及孔隙位置的迁移。有效应力的增大使得各孔隙半径均有减小,孔隙半径的减小比例分别与孔隙初始面积和孔隙的形状因子呈正相关关系和负相关关系。在相同的孔隙度条件下,孔隙半径越均匀,平均孔隙半径越小,应力敏感性越强。有效应力的增加使得岩心固有渗透率呈指数型下降且孔隙度越小、固有渗透率越低的岩心,其应力敏感性越强,孔隙度对固有渗透率的影响大于孔隙半径均匀性的影响。     

A fixed-parameter algorithm for minimum quartet inconsistency

Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the Minimum Quartet Inconsistency (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet topologies. The more general problem where we are not necessarily given a topology for every subset of four taxa appears to be fixed-parameter intractable. For MQI, however, which is also NP-complete, we can compute the required tree in time O(4^kn+n⁴). This means that the problem is fixed-parameter tractable and that in the case of a small number k of “errors” the tree reconstruction can be done efficiently. In particular, for minimal k, our algorithm can produce all solutions that resolve k errors. Additionally, we discuss significant heuristic improvements. Experiments underline the practical relevance of our solutions.     

数控车床免转位换刀暨刀位扩展装置的研制

分析安装在数控车床四方卧动转位刀架上的免转位换刀装置的功能,介绍该装置在免转位换刀的基础上实现刀位扩展的设计方案和结构特点。该装置结构简单,制造容易且成本低,使用方便。应用结果表明:在生产批量大、车削工序较多的车削工艺中使用该装置,能有效提高生产效率、降低成本。     

Computing the Quartet Distance between Evolutionary Trees in Time O( n log n)

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n ²).     

A Fast Quartet tree heuristic for hierarchical clustering

The Minimum Quartet Tree Cost problem is to construct an optimal weight tree from the weighted quartet topologies on n objects, where optimality means that the summed weight of the embedded quartet topologies is optimal (so it can be the case that the optimal tree embeds all quartets as nonoptimal topologies). We present a Monte Carlo heuristic, based on randomized hill-climbing, for approximating the optimal weight tree, given the quartet topology weights. The method repeatedly transforms a dendrogram, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. The problem and the solution heuristic has been extensively used for general hierarchical clustering of nontree-like (non-phylogeny) data in various domains and across domains with heterogeneous data. We also present a greatly improved heuristic, reducing the running time by a factor of order a thousand to ten thousand. All this is implemented and available, as part of the CompLearn package. We compare performance and running time of the original and improved versions with those of UPGMA, BioNJ, and NJ, as implemented in the SplitsTree package on genomic data for which the latter are optimized.     

Inferring evolutionary trees with strong combinatorial evidence

We consider the problem of inferring the evolutionary tree of a set of n species. We propose a quartet reconstruction method which specifically produces trees whose edges have strong combinatorial evidence. Let Q be a set of resolved quartets defined on the studied species, the method computes the unique maximum subset Q^* of Q which is equivalent to a tree and outputs the corresponding tree as an estimate of the species’ phylogeny. We use a characterization of the subset Q^* due to Bandelt and Dress (Adv. Appl. Math. 7 (1986) 309–343) to provide an O(n⁴) incremental algorithm for this variant of the NP-hard quartet consistency problem. Moreover, when chosing the resolution of the quartets by the four-point method (FPM) and considering the Cavender–Farris model of evolution, we show that the convergence rate of the Q^* method is at worst polynomial when the maximum evolutive distance between two species is bounded. We complete these theoretical results by an experimental study on real and simulated data sets. The results show that (i) as expected, the strong combinatorial constraints it imposes on each edge leads the Q^* method to propose very few incorrect edges; (ii) more surprisingly; the method infers trees with a relatively high degree of resolution.