Computer Engineering Commons^™

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 …

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 …

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 …

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

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 …

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

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.