From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time

We propose and study the Maximum Constrained Agreement Subtree (MCAST) problem, which is a variant of the classical Maximum Agreement Subtree (MAST) problem. Our problem allows users to apply their domain knowledge to control the construction of the agreement subtrees in order to get better results. We show that the MCAST problem can be reduced to the MAST problem in linear time and thus we have algorithms for MCAST with running times matching the fastest known algorithms for MAST. A preliminary version of this paper appears in the Proceedings of the Fifth Workshop on Algorithms in Bioinformatics (WABI 2005). Research of H.F. Ting is supported in part by Hong Kong RGC Grant HKU-7172/06E.     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

Region-Based Hierarchical Image Matching

This paper presents an approach to region-based hierarchical image matching, where, given two images, the goal is to identify the largest part in image 1 and its match in image 2 having the maximum similarity measure defined in terms of geometric and photometric properties of regions (e.g., area, boundary shape, and color), as well as region topology (e.g., recursive embedding of regions). To this end, each image is represented by a tree of recursively embedded regions, obtained by a multiscale segmentation algorithm. This allows us to pose image matching as the tree matching problem. To overcome imaging noise, one-to-one, many-to-one, and many-to-many node correspondences are allowed. The trees are first augmented with new nodes generated by merging adjacent sibling nodes, which produces directed acyclic graphs (DAGs). Then, transitive closures of the DAGs are constructed, and the tree matching problem reformulated as finding a bijection between the two transitive closures on DAGs, while preserving the connectivity and ancestor-descendant relationships of the original trees. The proposed approach is validated on real images showing similar objects, captured under different types of noise, including differences in lighting conditions, scales, or viewpoints, amidst limited occlusion and clutter.     

Information-theoretic Approaches Based on Sequential Monte Carlo to Collaborative Distributed Sensors for Mobile Robot Localization

We consider the Sequential Monte Carlo (SMC) method for Bayesian inference applied to the problem of information-theoretic distributed sensor collaboration in complex environments. The robot kinematics and sensor observation under consideration are described by nonlinear models. The exact solution to this problem is prohibitively complex due to the nonlinear nature of the system. The SMC method is, therefore, employed to track the probabilistic kinematics of the robot and to make the corresponding Bayesian estimates and predictions. To meet the specific requirements inherent in distributed sensors, such as low-communication consumption and collaborative information processing, we propose a novel SMC solution that makes use of the particle filter technique for data fusion, and the density tree representation of the a posterior distribution for information exchange between sensor nodes. Meanwhile, an efficient numerical method is proposed for approximating the information utility in sensor selection. A further experiment, obtained with a real robot in an indoor environment, illustrates that under the SMC framework, the optimal sensor selection and collaboration can be implemented naturally, and significant improvement in localization accuracy is achieved when compared to conventional methods using all sensors.     

AptaCDSS-E: A classifier ensemble-based clinical decision support system for cardiovascular disease level prediction

Conventional clinical decision support systems are generally based on a single classifier or a simple combination of these models, showing moderate performance. In this paper, we propose a classifier ensemble-based method for supporting the diagnosis of cardiovascular disease (CVD) based on aptamer chips. This AptaCDSS-E system overcomes conventional performance limitations by utilizing ensembles of different classifiers. Recent surveys show that CVD is one of the leading causes of death and that significant life savings can be achieved if precise diagnosis can be made. For CVD diagnosis, our system combines a set of four different classifiers with ensembles. Support vector machines and neural networks are adopted as base classifiers. Decision trees and Bayesian networks are also adopted to augment the system. Four aptamer-based biochip data sets including CVD data containing 66 samples were used to train and test the system. Three other supplementary data sets are used to alleviate data insufficiency. We investigated the effectiveness of the ensemble-based system with several different aggregation approaches by comparing the results with single classifier-based models. The prediction performance of the AptaCDSS-E system was assessed with a cross-validation test. The experimental results show that our system achieves high diagnosis accuracy (>94%) and comparably small prediction difference intervals (<6%), proving its usefulness in the clinical decision process of disease diagnosis. Additionally, 10 possible biomarkers are found for further investigation.     

后继序列有序的互关联后继树创建和搜索算法

研究针对全文检索领域的索引结构模型,基于二元互关联后继树模型,提出并实现了一个后继序列有序的后继树模型,然后利用此索引模型实现查询操作的优化。     

ID3算法在军事训练成绩分析中的应用

随着部队实战化训练的深入,传统的训练成绩分析方法已不能适应科学组训的需要。该文引入射击训练实例,应用人工智能中机器学习的ID3归纳学习算法,对射击情况进行分类分析,得出影响军事训练成绩的内部原因以及其他一些结论。     

低功耗SAR ADC的高性能比较器综述

目前逐次逼近型模数转换器(SAR ADC)已经成为低功耗数模混合集成电路中模数转换器的首选架构,其中的核心模块—高性能比较器的功耗大小直接决定了SAR ADC的整体功耗。文章从低功耗SAR ADC系统出发,聚焦高性能低功耗电压域和时间域比较器的发展历程与最新研究进展,总结了通过优化SAR逻辑实现低功耗比较器的技术方法。该综述为数模混合电路设计者了解并掌握SAR ADC中高性能低功耗比较器技术提供有力参考。     

基于PS-RRT算法的机械臂避障路径规划

针对应用快速搜索随机树（RRT）算法进行机械臂路径规划时,存在采样区域大、有效区域小、路径冗余节点多、剪枝时间长等问题,提出一种基于分区动态采样策略和重复区域节点拒绝机制的高效RRT路径规划算法PS-RRT（partitioned sampling RRT）。首先,通过PS-RRT快速规划机械臂末端初始路径;其次,分段检测机械臂跟随该路径时的连杆碰撞情况,对碰撞路段进行带臂形约束的第二次规划;最后,将初始路径和第二次规划的路径拼接后进行路径裁剪。将所提方法在多种场景中进行仿真验证,结果表明：基于PS-RRT算法的机械臂避障路径规划策略使得无效节点数大幅减少,可高效规划出机械臂的无碰路径,验证了算法的可行性。