Computer Engineering Commons^™

Agents And Service-Oriented Computing For Autonomic Computing: A Research Agenda, Frances M.T. Brazier, Jeffrey O. Kephart, H. Van Dyke Parunak, Michael N. Huhns

Faculty Publications

Autonomic computing is the solution proposed to cope with the complexity of today's computing environments. Self-management, an important element of autonomic computing, is also characteristic of single and multiagent systems, as well as systems based on service-oriented architectures. Combining these technologies can be profitable for all - in particular, for the development of autonomic computing systems.

Gene Order Phylogeny Of The Genus Prochlorococcus, Haiwei Luo, Jian Shi, William Arndt, Jijun Tang, Robert Friedman

Faculty Publications

Background
Using gene order as a phylogenetic character has the potential to resolve previously unresolved species relationships. This character was used to resolve the evolutionary history within the genus Prochlorococcus, a group of marine cyanobacteria.

Methodology/Principal Findings
Orthologous gene sets and their genomic positions were identified from 12 species of Prochlorococcus and 1 outgroup species of Synechococcus. From this data, inversion and breakpoint distance-based phylogenetic trees were computed by GRAPPA and FastME. Statistical support of the resulting topology was obtained by application of a 50% jackknife resampling technique. The result was consistent and congruent with nucleotide sequence-based and gene-content based …

A Special-Purpose Architecture For Solving The Breakpoint Median Problem, Jason D. Bakos, Panormitis E. Elenis

Faculty Publications

In this paper, we describe the design for a co-processor for whole-genome phylogenetic reconstruction. Our current design performs a parallelized breakpoint median computation, which is an expensive component of the overall application. When implemented on a field-programmable gate array (FPGA), our hardware breakpoint median achieves a maximum speedup of 1005times over software. When the coprocessor is used to accelerate the entire reconstruction procedure, we achieve a maximum application speedup of 417times. The results in this paper suggest that FPGA-based acceleration is a promising approach for computationally expensive phylogenetic problems, in spite of the fact that the involved algorithms are based …

Multi-Break Rearrangements And Breakpoint Re-Uses: From Circular To Linear Genomes, Max A. Alekseyev

Faculty Publications

Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While 2-break rearrangements represent standard reversals, fusions, fissions, and translocations, 3-break rearrangements represent a natural generalization of transpositions. Alekseyev and Pevzner (2007a, 2008a) studied multi-break rearrangements in circular genomes and further applied them to the analysis of chromosomal evolution in mammalian genomes. In this paper, we extend these results to the more difficult case of linear genomes. In particular, we give lower bounds for the rearrangement distance between linear genomes and for the breakpoint re-use rate as functions of the number and proportion …

Improving Reversal Median Computation Using Commuting Reversals And Cycle Information, William Arndt, Jijun Tang

Faculty Publications

In the past decade, genome rearrangements have attracted increasing attention from both biologists and computer scientists as a new type of data for phylogenetic analysis. Methods for reconstructing phylogeny from genome rearrangements include distance-based methods, MCMC methods, and direct optimization methods. The latter, pioneered by Sankoff and extended with the software suites GRAPPA and MGR, is the most accurate approach, but is very limited due to the difficulty of its scoring procedure—it must solve multiple instances of the reversal median problem to compute the score of a given tree. The reversal median problem is known to be NP-hard and all …

Evaluating Shape Correspondence For Statistical Shape Analysis: A Benchmark Study, Brent C. Munsell, Pahal Dalal, Song Wang

Faculty Publications

This paper introduces a new benchmark study to evaluate the performance of landmark-based shape correspondence used for statistical shape analysis. Different from previous shape-correspondence evaluation methods, the proposed benchmark first generates a large set of synthetic shape instances by randomly sampling a given statistical shape model that defines a ground-truth shape space. We then run a test shape-correspondence algorithm on these synthetic shape instances to identify a set of corresponded landmarks. According to the identified corresponded landmarks, we construct a new statistical shape model, which defines a new shape space. We finally compare this new shape space against the ground-truth …

Phylogenetic Reconstruction From Transpositions, Feng Yue, Meng Zhang, Jijun Tang

Faculty Publications

Background
Because of the advent of high-throughput sequencing and the consequent reduction in the cost of sequencing, many organisms have been completely sequenced and most of their genes identified. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the rearrangement of these entities through computational means. As a result, genome rearrangement data has attracted increasing attentions from both biologists and computer scientists as a new type of data for phylogenetic analysis. The main events of genome rearrangements include inversions, transpositions and transversions. To date, GRAPPA and MGR are the most accurate …

Gene Rearrangement Analysis And Ancestral Order Inference From Chloroplast Genomes With Inverted Repeat, Feng Yue, Liying Cui, Claude W. Depamphilis, Bernard M.E. Moret, Jijun Tang

Faculty Publications

Background
Genome evolution is shaped not only by nucleotide substitutions, but also by structural changes including gene and genome duplications, insertions, deletions and gene order rearrangements. The most popular methods for reconstructing phylogeny from genome rearrangements include GRAPPA and MGR. However these methods are limited to cases where equal gene content or few deletions can be assumed. Since conserved duplicated regions are present in many chloroplast genomes, the inference of inverted repeats is needed in chloroplast phylogeny analysis and ancestral genome reconstruction.

Results
We extend GRAPPA and develop a new method GRAPPA-IR to handle chloroplast genomes. A test of GRAPPA-IR …

Comparing Discrimination And Cfa For Selecting Tracking Features, Damian M. Lyons, D. Frank Hsu

Faculty Publications

The ability of a tracker to isolate the foreground target from the background of an image is crucially dependent on the set of features selected for tracking. Collins & Liu [2] propose an on-line, adaptive approach to selecting the set of features based on the insight that the set of features that best discriminate between target and background classes is the best set to use for tracking. In previous work [10], we have proposed an approach based on Combinatorial Fusion Analysis for selecting features for Real-Time tracking. We discuss the relative merits of the two methods and motivate their combination …

Efficient Peer Assignment For Low-Latency Transmission Of Scalable Coded Images, Xiao Su, Tao Wang

Faculty Publications

In this paper, we propose efficient peer assignment algorithms for low-latency transmission of scalable coded images in peer-to-peer networks, in which peers may dynamically join and leave the networks. The objective of our algorithm is to minimize the transmission time of a requested image that is scalable coded. When an image is scalable coded in different bit rates, the bit stream encoded in a lower bit rate is a prefix subset of the one encoded in a higher bit rate. Therefore, a peer with the same requested image coded in any bit rate, even when it is different from the …

Globally Optimal Grouping For Symmetric Closed Boundaries By Combining Boundary And Region Information, Joachim S. Stahl, Song Wang

Faculty Publications

Many natural and man-made structures have a boundary that shows a certain level of bilateral symmetry, a property that plays an important role in both human and computer vision. In this paper, we present a new grouping method for detecting closed boundaries with symmetry. We first construct a new type of grouping token in the form of symmetric trapezoids by pairing line segments detected from the image. A closed boundary can then be achieved by connecting some trapezoids with a sequence of gap-filling quadrilaterals. For such a closed boundary, we define a unified grouping cost function in a ratio form: …

Web-Scale Workflow: Integrating Distributed Services, M. Brian Blake, Michael N. Huhns

Faculty Publications

Modular applications, components, and services are all ways of describing the product of an organization's efforts to embody its capabilities in autonomous software modules. In fact, the integration of services using well-established workflow paradigms could amplify an organization's capabilities with the creation of a full-blown, inter-organizational system of systems. This is the essence of Web-scale workflows. Considering the recent popularity and acceptance of service-oriented technologies, the application of such distributed systems is only limited by imagination, but it's also important to understand existing research challenges and their implications to various Web-scale workflow domains.

Network Formation Using Ant Colony Optimization -- A Systematic Review, Steven C. Oimoen, Gilbert L. Peterson, Kenneth M. Hopkinson

Faculty Publications

A significant area of research in the field of hybrid communications is the Network Design Problem (NDP) [1]. The NDP is an NP complete problem [1] that focuses on identifying the optimal network topology for transmitting commodities between nodes, under constraints such as bandwidth, limited compatible directed channels, and link and commodity costs. The NDP focuses on designing a flexible network while trying to achieve optimal flow or routing. If a link (or arc) is used, then an associated fixed cost of the edge is incurred. In addition, there is a cost for using the arc depending on the flow. …

A Survey Of Worm Detection And Containment, Pele Li, M. Salour, Xiao Su

Faculty Publications

Self-duplicating, self-propagating malicious codes known as computer worms spread themselves without any human interaction and launch the most destructive attacks against computer networks. At the same time, being fully automated makes their behavior repetitious and predictable. This article presents a survey and comparison of Internet worm detection and containment schemes. We first identify worm characteristics through their behavior, and then classify worm detection algorithms based on the parameters used in the algorithms. Furthermore, we analyze and compare different detection algorithms with reference to the worm characteristics by identifying the type of worms that can and cannot be detected by these …

Are There Rearrangement Hotspots In The Human Genome?, Max A. Alekseyev, Pavel A. Pevzner

Faculty Publications

In a landmark paper, Nadeau and Taylor [18] formulated the random breakage model (RBM) of chromosome evolution that postulates that there are no rearrangement hotspots in the human genome. In the next two decades, numerous studies with progressively increasing levels of resolution made RBM the de facto theory of chromosome evolution. Despite the fact that RBM had prophetic prediction power, it was recently refuted by Pevzner and Tesler [4], who introduced the fragile breakage model (FBM), postulating that the human genome is a mosaic of solid regions (with low propensity for rearrangements) and fragile regions (rearrangement hotspots). However, the rebuttal …

Web Site Personalization Based On Link Analysis And Navigational Patterns, Magdalini Eirinaki, M. Varzirgiannis

Faculty Publications

The continuous growth in the size and use of the World Wide Web imposes new methods of design and development of on-line information services. The need for predicting the users’ needs in order to improve the usability and user retention of a web site is more than evident and can be addressed by personalizing it. Recommendation algorithms aim at proposing “next” pages to users based on their current visit and the past users’ navigational patterns. In the vast majority of related algorithms, however, only the usage data are used to produce recommendations, disregarding the structural properties of the web graph. …

Edge Grouping Combining Boundary And Region Information, Joachim S. Stahl, Song Wang

Faculty Publications

This paper introduces a new edge-grouping method to detect perceptually salient structures in noisy images. Specifically, we define a new grouping cost function in a ratio form, where the numerator measures the boundary proximity of the resulting structure and the denominator measures the area of the resulting structure. This area term introduces a preference towards detecting larger-size structures and, therefore, makes the resulting edge grouping more robust to image noise. To find the optimal edge grouping with the minimum grouping cost, we develop a special graph model with two different kinds of edges and then reduce the grouping problem to …

Localization With Limited Sensing, Jason M. O'Kane, Steven M. Lavalle

Faculty Publications

Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes the lower limits of this range by describing three extremely simple robot models and addresses the active localization problem for each. The robot, whose configuration is composed of its position and orientation, moves in a fully-known, simply connected polygonal environment. We pose the localization task as a planning problem in the robot's information space, which encapsulates the uncertainty in the robot's configuration. We consider robots equipped with: 1) angular and linear …

Extended Abstract Rotopod: A Novel Approach To Efficient Legged Locomotion, Damian M. Lyons

Faculty Publications

A number of attempts have been made to integrate the efficiency of wheeled locomotion with the terrain versatility of legged locomotion, e.g., Univ.Michigan’s Rhex platform and Case Western’s Whegs. Those platforms cast legs as rotating spokes placed traditionally at the corners of a rectangular platform. In this paper, we present an alternate approach, with three legs radiating down from a central hub. The energy to move the platform is generated by a rotating reaction mass mounted at the hub and, at rest, rotating parallel to the ground plane.

Our approach is to construct a platform whose natural, uncontrolled motion is …

Evaluation Of A Parallel Architecture And Algorithm For Mapping And Localization, Damian M. Lyons, Giselle R. Isner

Faculty Publications

The Beowulf cluster approach to parallel computation offers a potentially cheap and robust source of computational power for high complexity algorithms in robotics. The challenge is to integrate this approach with the mobility and time critical response constraints of many robotic algorithms. The key contributions of this paper are: (1) introduction of a computational architecture for integrating a cluster into the control architecture of one or more robots, (2) a cluster implementation of Thrun et al’s Concurrent Localization and Mapping (CML) algorithm, and (3) presentation of results to illustrate the performance of the implemented CML algorithm and validate the architectural …

Combinatorial Fusion Criteria For Robot Mapping, Damian M. Lyons, D. Frank Hsu, Qiang Ma, Liang Wang

Faculty Publications

We address the problem of sensor fusion for stereo and ultrasound depth measurements for map building for a robot operating in a cluttered environment. In such a situation it’s difficult to make useful and realistic assumpt ions about the sensor or environment statistics. Combinatorial Fusion Analysis is used to develop an approach to fusion with unknown sensor and environment statistics. A metric is proposed that shows when fusion from a set of fusion alternatives will produ ce a more accurate estimation of depth than either sonar or stereo alone and when not. The metric consists of two crit eria: (a) …

Selection Of Fusion Operations Using Rank-Score Diversity For Robot Mapping And Localization, Damian M. Lyons, D. Frank Hsu, Qiang Ma, Liang Wang

Faculty Publications

In this paper, we evaluate the use of a rank-score diversity measure for selecting sensory fusion operations for a robot localization and mapping application. Our current application involves robot mapping and navigation in an outdoor urban search and rescue situation in which we have many similar and mutually occluding landmarks. The robot is a 4- wheel direct drive platform equipped with visual, stereo depth and ultrasound sensors. In such an application it’s difficult to make useful and realistic assumptions about the sensor or environment statistics. Combinatorial Fusion Analysis(CFA) is used to develop an approach to fusion with unknown sensor and …

Fpga Acceleration Of Gene Rearrangement Analysis, Jason D. Bakos

Faculty Publications

In this paper we present our work toward FPGA acceleration of phylogenetic reconstruction, a type of analysis that is commonly performed in the fields of systematic biology and comparative genomics. In our initial study, we have targeted a specific application that reconstructs maximum-parsimony (MP) phylogenies for gene-rearrangement data. Like other prevalent applications in computational biology, this application relies on a control-dependent, memory-intensive, and non-arithmetic combinatorial optimization algorithm. To achieve hardware acceleration, we developed an FPGA core design that implements the application's primary bottleneck computation. Because our core is lightweight, we are able to synthesize multiple cores on a single FPGA. …

Lightweight Error Correction Coding For System-Level Interconnects, Jason D. Bakos, Donald M. Chiarulli, Steven P. Levitan

Faculty Publications

"Lightweight hierarchical error control coding (LHECC)" is a new class of nonlinear block codes that is designed to increase noise immunity and decrease error rate for high-performance chip-to-chip and on-chip interconnects. LHECC is designed such that its corresponding encoder and decoder logic may be tightly integrated into compact, high-speed, and low-latency I/O interfaces. LHECC operates over a new channel technology called multi-bit differential signaling (MBDS). MBDS channels utilize a physical-layer channel code called "N choose M (nCm)" encoding, where each channel is restricted to a symbol set such that half of the bits in each symbol are set to one. …

Whole Genome Duplications And Contracted Breakpoint Graphs, Max A. Alekseyev, Pavel A. Pevzner

Faculty Publications

The genome halving problem, motivated by the whole genome duplication events in molecular evolution, was solved by El-Mabrouk and Sankoff in the pioneering paper [SIAM J. Comput., 32 (2003), pp. 754–792]. The El-Mabrouk–Sankoff algorithm is rather complex, inspiring a quest for a simpler solution. An alternative approach to the genome halving problem based on the notion of the contracted breakpoint graph was recently proposed in [M. A. Alekseyev and P. A. Pevzner, IEEE/ACM Trans. Comput. Biol. Bioinformatics, 4 (2007), pp. 98–107]. This new technique reveals that while the El-Mabrouk–Sankoff result is correct in most cases, it does not hold in …

Colored De Bruijn Graphs And The Genome Halving Problem, Max A. Alekseyev, Pavel A. Pevzner

Faculty Publications

Breakpoint graph analysis is a key algorithmic technique in studies of genome rearrangements. However, breakpoint graphs are defined only for genomes without duplicated genes, thus limiting their applications in rearrangement analysis. We discuss a connection between the breakpoint graphs and de Bruijn graphs that leads to a generalization of the notion of breakpoint graph for genomes with duplicated genes. We further use the generalized breakpoint graphs to study the Genome Halving Problem (first introduced and solved by Nadia El-Mabrouk and David Sankoff). The El-Mabrouk-Sankoff algorithm is rather complex, and, in this paper, we present an alternative approach that is based …

A Cognitive Robotics Approach To Comprehending Human Language And Behaviors, Deryle W. Lonsdale, D. Paul Benjamin, Damian Lyons

Faculty Publications

The ADAPT project is a collaboration of researchers in linguistics, robotics and artificial intelligence at three universities. We are building a complete robotic cognitive architecture for a mobile robot designed to interact with humans in a range of environments, and which uses natural language and models human behavior. This paper concentrates on the HRI aspects of ADAPT, and especially on how ADAPT models and interacts with humans.

Sequence Of Linear Programming For Transmission Of Fine-Scalable Coded Content In Bandwidth-Limited Environments, Xiao Su, Tao Wang

Faculty Publications

In this paper, we propose an optimal peer assignment algorithm on peer-to-peer networks. This algorithm is designed to maximize the quality of transmitting fine-scalable coded content by exploiting the embedding property of scalable coding. To be more realistic, we assume that the requesting peer has a delay constraint to display the content within a certain delay bound, and it also has limited incoming bandwidth. We first use a simple example to illustrate the peer assignment problem, and then formulate this problem as a linear programming problem, followed by a nonlinear programming problem. To efficiently solve the second nonlinear problem, we …

Combining Multiple Scoring Systems For Video Target Tracking Based On Rank-Score Function Variation, D. Frank Hsu, Damian M. Lyons, Jizhou Ai

Faculty Publications

Tracking of video targets is the process of estimating the current and predicting the future state of a target from a sequence of video sensor measurements. Multitarget video tracking is complicated by the fact that targets can occlude one another and affect video feature measurements in a highly non-linear and difficult to model fashion., Tracking multiple targets that undergo repeated mutual occlusions is a challenging problem with several issues to be addressed. In this paper we propose a multisensory fusion approach to the problem of multitarget video tracking with occlusion. Each sensory cue is treated as a scoring system on …

Combinatorial Fusion Criteria For Real-Time Tracking, D. Frank Hsu, Damian M. Lyons, Jizhou Ai

Faculty Publications

We address the problem of automated video tracking of targets when targets undergo multiple mutual occlusions. Our approach is based on the idea that as targets are occluded, selection of feature subsets and combinations of those features are effective in identifying the target and improving tracking performance. We use Combinatorial Fusion Analysis to develop a metric to select which subset of features will produce the most accurate tracking. In particular we show that the combination of a pair of features A and B will improve the accuracy only if (a) A and B have relative high performance, and (b) A …