Open Access. Powered by Scholars. Published by Universities.®

Engineering Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Engineering

University of South Carolina

Series

2007

Articles 1 - 7 of 7

Full-Text Articles in Engineering

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

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 …

Go to article

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

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 …

Go to article

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

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 …

Go to article

Fpga Acceleration Of Gene Rearrangement Analysis, Jason D. Bakos Apr 2007

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

Go to article

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

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

Go to article

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

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 …

Go to article

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

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 …

Go to article