Computer Engineering Commons^™

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. …

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.

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 …