Home | Research | Teaching |  Publications  

Research Projects - Computational Biology

 Non-unique Probe Selection and Group Testing

A probe is a short oligonucleotide of size 8-25, used for identifying viruses in a biological sample through
hybridization. An important minimization problem in molecular biology is to select minimum number of probes to identify the presence or absence of up to a certain amount of viruses. When each probe hybridizes to a unique virus, identification is straightforward. However, unique probes are very hard to obtain, especially for virus subtypes which are closely related. In this work, we proved that the minimization problem is MAX SNP-complete when every probe hybridizes at most to two viruses, and proposed a polynomial-time approximation with approximation ratio of 1+2/(d+1), where d is the number of identified viruses.
Moreover, we proved that the minimization problem is polynomial-time solvable when every probe hybridizes exactly to two viruses. This work has been submitted to Theoretical Computer Science, 2007.

DNA Library Screening and Pooling Design

High-quality DNA libraries are obtained through a large amount of DNA testing and screening. Therefore, the
efficiency of DNA testing and screening becomes very important. Pooling design is a tool to reduce the number of tests in DNA library screening. we proposed an improved construction which is near optimal for classic pooling designs. This work has been accepted for publication in Journal of Combinatorial Optimization, 2007

Research Projects - Wireless Networks

     Greedy Construction of Connected Dominating Sets

Inspired by the backbone in wired networks, Virtual Backbone has been used as the routing infrastructure for wireless ad hoc networks to reduce the communication overhead and simplify the connectivity management. A Connected Dominating Set (CDS) of the graph representing the network is a good candidate for Virtual Backbone. How to construct a Minimum Connected Dominating Set (MCDS), which has been proven to be NP-hard, is an important and interesting problem. We proposed a Steiner tree based greedy algorithm, called S-MIS to construct a CDS within a factor of 4.8+ln5 from the optimal solution. This approximation ratio outperforms the previous best approximation ratio which is 6.8. We also proposed the distributed version of S-MIS algorithm. This work has been published in Journal of Wireless Communications and Mobile Computing, Special Issue on Ad Hoc Networks, 2005.

     Stable Virtual Backbone

Virtual Backbone can help reduce the communication overhead and simplify the connectivity management in wireless networks. However, the virtual backbone structure is very vulnerable in mobile environment. We tackled the mobility issue by proactively considering node stability and coverage during the backbone construction process and proposed a distributed Connected Maximal Independent Set (CMIS) algorithm with an approximation ratio of 8 for backbone construction. Furthermore, we deployed a practical mobility model by modifying the widely used Random way-point model (RWP) to model the mobility of the wireless node and showed that CMIS could result an 88\% increase of the connectivity lifetime against equivalent backbone size. The distributed CMIS algorithm has been published on IEEE International conference on Mobile Ad Hoc and Sensor Systems (MASS), 2004. The localized version has been published on IEEE International Performance Computing and Communications Conference (IPCCC), 2005.

     Fault Tolerant Virtual Backbone

Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. We proposed a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We proved that CDSA has constant approximation ratio. We also demonstrated the node size of the 2-connected virtual backbone constructed by CDSA is only 5% larger than the size of a 1-connected backbone. This work has been submitted to IEEE Transactions on Wireless Communications, 2006 and currently is undergoing a major revision.

     Connected Dominating Set for Different Transmission Ranges

Connected Dominating Set has been studied extensively in Unit Disk Graphs (UDG), in which each node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessary equal. We modelled a network as a disk graph and introduce the CDS problem in disk graphs. We presented three constant approximation algorithms to obtain a CDS of a given network and also gave their distributed versions. In addition, we studied the relationship between the size of an independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. This work has been accepted for publication by IEEE Transactions on Mobile Computing, 2007.

     Fault Tolerant Topology Control

Fault tolerant topology control, that is, how to provide fault tolerance while minimizing total node power consumption in wireless network is a very challenging problem. We introduced and studied the problem of fault tolerant topology control for all-to-one and one-to-all communication model in static wireless networks. We modelled the networks with asymmetric wireless links with directed graph and investigated two approaches, namely minimum weight based approach and nearest neighbor augmentation approach. We proved that the minimum weight based approach has a k-approximation algorithm for all-to-one fault tolerant topology control where k is the number of disjoint paths. When k = 1, this approach gave a polynomial time solution for the minimum power sink tree problem. We also studied the one-to-all fault tolerant topology control problem in symmetric wireless networks which can be modelled using an undirected graph. We prove that minimum weight based approach is a 4k approximation and the nearest neighbor augmentation approach is a (k+4) approximation. This work for asymmetric wireless links is undergoing a major revision by IEEE Transactions on Mobile Computing 2006. The work for symmetric wireless links has been accepted for publication by International Journal of Sensor Networks, Special Issue on Theoretical and Algorithm Aspects on Sensor Networks, 2007.

     Broadcast Tree Construction

Energy conservation is an important concern in wireless networks. Many algorithms for constructing a broadcast tree with minimum energy consumption and other goals have been developed. However, no previous research work considers the total energy consumption and transmission delays of the broadcast tree simultaneously. In this work, based on (\alpha,\beta)-tree, a novel concept to wireless networks, we defined a new Strongly connected Broadcast Arborescence with bounded Transmission delay (SBAT) problem and design the Strongly connected Broadcast Arborescence (SBA) algorithm with linear running time to construct a strongly connected broadcast tree with bounded total power, while satisfying the constraint that the transmission delays between the source and the other hosts are also bounded. We also proposed the distributed version and gave theoretical performance ratio analysis. This work has been published in IEEE Transactions on Mobile Computing, 2006.