Computer Engineering Commons^™

Research On Approximate Bayesian Computation, Jiting Xu

Theses and Dissertations

This thesis presents the development of a new numerical algorithm for statistical inference problems that require sampling from distributions which are intractable. We propose to develop our sampling algorithm based on a class of Monte Carlo methods, Approximate Bayesian Computation (ABC), which are specifically designed to deal with this type of likelihood-free inference. ABC has become a fundamental tool for the analysis of complex models when the likelihood function is computationally intractable or challenging to mathematically specify. The central theme of our approach is to enhance the current ABC algorithms by exploiting the structure of the mathematical models via derivative …

Ghosts Of The Horseshoe, Heidi Rae Cooley, Richard Walker, Duncan Buell

Digital Projects

Ghosts of the Horseshoe (Ghosts) is a mobile interactive application that endeavors to bring into view--literally, on mobile micro screens (iPads and iPhones at present)--the largely unknown history of slavery at South Carolina College. It deploys game mechanics (i.e., ludic methods), as well as Augmented Reality (AR) and GPS functionality to generate awareness of and questioning about what otherwise seems ordinary: a grassy space at the center of a university campus. It organizes content into distinct but overlapping themes: (1) architectural ghosts (e.g., razed outbuildings); (2) human ghosts (e.g., un/named enslaved persons); and (3) the historic Wall delimiting the Horseshoe …

Toward A Framework For Levels Of Robot Autonomy In Human-Robot Interaction, Jenay Beer, A. D. Fisk, W. A. Rogers

Faculty Publications

Autonomy is a critical construct related to human-robot interaction (HRI) and varies widely across robot platforms. Levels of robot autonomy (LORA), ranging from teleoperation to fully autonomous systems, influence the way in which humans and robots interact with one another. Thus, there is a need to understand HRI by identifying variables that influence—and are influenced by—robot autonomy. Our overarching goal is to develop a framework for LORA in HRI. To reach this goal, our framework draws links between HRI and human-automation interaction, a field with a long history of studying and understanding human-related variables. The construct of autonomy is reviewed …

Secure And Reliable Wireless Communication Through End-To-End-Based Solution, Hossen Asiful Mustafa

Theses and Dissertations

In the past few decades, network architectures and protocols are often designed to achieve a high throughput and a low latency. Security was rarely considered during the initial design phases. As a result, many network systems are insecure by design. Once they are widely deployed, the inherent vulnerabilities may be difficult to eliminate due to the prohibitive update cost. In this dissertation, we examine such types of vulnerabilities in various networks and design end-to-end-based solutions that allow end systems to address such loopholes.

The end-to-end argument was originally proposed to let end hosts implement application-specific functions rather than letting intermediate …

A Multiagent Approach Towards Solving Complex Problems Of Sociotechnical Systems, Hongying Du

Theses and Dissertations

Complex resource allocation problems arise due to complex human societies and scarce resources to be distributed. Scarce resources could be food, water, and energy. Meanwhile, the size of the problem, the intersection of different areas, and possible global consequences all add to the complexity of the problems, which makes it difficult for humans to solve the problems by themselves.

For all these reasons, humans need technical help to tackle complex problems. Since humans participating in the problems usually own part of the information about the problems, and no one may see the whole picture of the problems, it is natural …

Advances In The Redcat Software Package, Chris Schmidt, Stephanie J. Irausquin, Homayoun Valafar

Faculty Publications

Background

Residual Dipolar Couplings (RDCs) have emerged in the past two decades as an informative source of experimental restraints for the study of structure and dynamics of biological macromolecules and complexes. The REDCAT software package was previously introduced for the analysis of molecular structures using RDC data. Here we report additional features that have been included in this software package in order to expand the scope of its analyses. We first discuss the features that enhance REDCATs user-friendly nature, such as the integration of a number of analyses into one single operation and enabling convenient examination of a structural ensemble …

Protein Structure Validation And Identification From Unassigned Residual Dipolar Coupling Data Using 2d-Pdpa, Arjang Fahim, Rishi Mukhopadhyay, Ryan Yandle, James H. Prestegard, Homayoun Valafar

Faculty Publications

More than 90% of protein structures submitted to the PDB each year are homologous to some previously characterized protein structure. The extensive resources that are required for structural characterization of proteins can be justified for the 10% of the novel structures, but not for the remaining 90%. This report presents the 2D-PDPA method, which utilizes unassigned residual dipolar coupling in order to address the economics of structure determination of routine proteins by reducing the data acquisition and processing time. 2D-PDPA has been demonstrated to successfully identify the correct structure of an array of proteins that range from 46 to 445 …

A Forward-Secure Certificate-Based Signature Scheme, Jiguo Li, Huiyun Teng, Xinyu Huang, Yichen Zhang, Jianying Zhou

Faculty Publications

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure raises a serious concern. In an effort to address the key exposure problem, the notion of forward security was first presented by Günther in 1990. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the secret key corresponding to a given time period does not enable an adversary to ‘break’ the scheme for any prior time period. In this paper, we first introduce forward security into certificate-based cryptography and define the security model of forward-secure certificate-based signatures (CBSs). …

Path Loss In An Urban Peer-To-Peer Channel For Six Public-Safety Frequency Bands, David W. Matolak, Qian Zhang, Qiong Wu

Faculty Publications

We provide path loss data and models for a peer-to-peer wireless channel for an urban environment in six public safety bands, for simultaneous transmission to five spatially separated receiving sites. Results are from measurements in Denver, Colorado. The six frequencies at which we measured are (in MHz) 430, 750, 905, 1834, 2400, and 4860. Both line-of-sight and non-line-of-sight conditions were covered, and we quantify path loss exponents and linear-fit standard deviations as functions of frequency and location. Line-of-sight results agree with prior work, but non-line-of-sight exponents, from 3.6-7.3, are generally larger than in most other references.

Phylogeny And Ancestral Genome Reconstruction From Gene Order Using Maximum Likelihood And Binary Encoding, Fei Hu

Theses and Dissertations

Over the long history of genome evolution, genes get rearranged under events such as rearrangements, losses, insertions and duplications, which in all change the ordering and content along the genome. Recent progress in genome-scale sequencing renews the challenges in the reconstructions of phylogeny and ancestral genomes with gene-order data. Such problems have been proved so interesting that a large number of algorithms have been developed rigorously over the past few years in attempts to tackle these problems following various principles. However, difficulties and limitations in performance and scalability largely prevent us from analyzing emerging modern whole-genome data, our study presented …

Computational Analysis And Prediction Of Genome-Wide Protein Targeting Signals And Localization, Jhih-Rong Lin

Theses and Dissertations

Computational prediction of protein subcellular localization can greatly help to elucidate its functions. Despite the existence of dozens of protein localization prediction algorithms, the prediction accuracy and coverage are still low. Several ensemble algorithms have been proposed to improve the prediction performance, which usually include as many as 10 or more individual localization algorithms. However, their performance is still limited by the running complexity and redundancy among individual prediction algorithms. In the first part of the dissertation, we propose a novel method for rational design of minimalist ensemble algorithms for practical genome-wide protein subcellular localization prediction. The algorithm is based …

Improving Robustness And Scalability Of Available Ner Systems, Amber Mckenzie

Theses and Dissertations

The focus of this research is to study and develop techniques to adapt existing NER resources to serve the needs of a broad range of organizations without expert NLP manpower. My methods emphasize usability, robustness and scalability of existing NER systems to ensure maximum functionality to a broad range of organizations. Usability is facilitated by ensuring that the methodologies are compatible with any available open-source NER tagger or data set, thus allowing organizations to choose resources that are easy to deploy and maintain and fit their requirements. One way of making use of available tagged data would be to aggregate …

Accuracy, Cost And Performance Trade-Offs For Streaming Set-Wise Floating Point Accumulation On Fpgas, Krishna Kumar Nagar

Theses and Dissertations

The set-wise summation operation is perhaps one of the most fundamental and widely used operations in scientific applications. In these applications, maintaining the accuracy of the summation is also important as floating point operations have inherent errors associated with them. Designing floating-point accumulators presents a unique set of challenges: double-precision addition is usually deeply pipelined and without special micro-architectural or data scheduling techniques, the data hazard that exists. There have been several efforts to design floating point accumulators and accurate summation architecture using different algorithms on FPGAs but these problems have been dealt with separately. In this dissertation, we present …

An Application For Keeping Track Of Food Item Expiration, Rejin Paul James

Theses and Dissertations

Food, honestly, is too precious to waste. Food wastage is a very serious issue prevalent in the world today. American households alone throw out an equivalent of $165 billion worth of food each year. People often forget to consume food they purchased before the expiration date, or sometimes they over-purchase food they can have, then throw them away. Hence, this thesis aims to prevent food wastage with the help of a smart phone application that helps keep track of food item expiration dates and gives you notification alerts when it is about to expire. It implements a barcode scanner for …

Wireless Networks-On-Chips: Architecture, Wireless Channel, And Devices, David W. Matolak, Avinash Kodi, Savas Kaya, Dominic Ditomaso, Soumyasanta Laha, William Rayess

Faculty Publications

Wireless networks-on-chips (WINoCs) hold substantial promise for enhancing multicore integrated circuit performance, by augmenting conventional wired interconnects. As the number of cores per IC grows, intercore communication requirements will also grow, and WINoCs can be used to both save power and reduce latency. In this article, we briefly describe some of the key challenges with WINoC implementation, and also describe our example design, iWISE, which is a scalable wireless interconnect design. We show that the integration of wireless interconnects with wired interconnects in NoCs can reduce overall network power by 34 percent while achieving a speedup of 2.54 on real …

Multiple Structure Alignment With Mstali, Paul Shealy, Homayoun Valafar

Faculty Publications

Background

Multiple structure alignments have received increasing attention in recent years as an alternative to multiple sequence alignments. Although multiple structure alignment algorithms can potentially be applied to a number of problems, they have primarily been used for protein core identification. A method that is capable of solving a variety of problems using structure comparison is still absent. Here we introduce a program msTALI for aligning multiple protein structures. Our algorithm uses several informative features to guide its alignments: torsion angles, backbone C^α atom positions, secondary structure, residue type, surface accessibility, and properties of nearby atoms. The algorithm allows …

Worse-Than-Rayleigh Fading: Experimental Results And Theoretical Models, David W. Matolak, Jeff Frolik

Faculty Publications

This article is motivated by the recent recognition that channel fading for new wireless applications is not always well described by traditional models used for mobile communication systems. In particular, fading data collected for vehicleto- vehicle and wireless sensor network applications has motivated new models for conditions in which channel fading statistics can be worse than Rayleigh. We review the use of statistical channel models, describe our example applications, and provide both measured and modeling results for these severe fading conditions.

5 Ghz Band Vehicle-To-Vehicle Channels: Models For Multiple Values Of Channel Bandwidth, Qiong Wu, David W. Matolak, Indranil Sen

Faculty Publications

In Sen and Matolak's earlier paper, 5-GHz-band vehicle-to-vehicle (V2V) channel models were presented for channel bandwidths of 5 and 10 MHz. In this paper, we provide additional tapped delay line models for bandwidths of 1, 20, 33.33, and 50 MHz based upon the data used in Sen and Matolak's paper. We provide tables of channel parameters for five types of V2V channel classes and also include example tap correlation coefficients. Root-mean-square delay spread values are summarized, as are values of bandwidth for which the channel frequency correlation takes values of 0.7 and 0.5. As with the results from Sen and …

Fpga Acceleration Of The Phylogenetic Likelihood Function For Bayesian Mcmc Inference Methods, Stephanie Zierke, Jason D. Bakos

Faculty Publications

Background
Likelihood (ML)-based phylogenetic inference has become a popular method for estimating the evolutionary relationships among species based on genomic sequence data. This method is used in applications such as RAxML, GARLI, MrBayes, PAML, and PAUP. The Phylogenetic Likelihood Function (PLF) is an important kernel computation for this method. The PLF consists of a loop with no conditional behavior or dependencies between iterations. As such it contains a high potential for exploiting parallelism using micro-architectural techniques. In this paper, we describe a technique for mapping the PLF and supporting logic onto a Field Programmable Gate Array (FPGA)-based co-processor. By leveraging …

Reverberation-Chamber Test Environment For Outdoor Urban Wireless Propagation Studies, Helge Fielitz, Kate A. Remley, Christopher L. Holloway, Qian Zhang, Qiong Wu, David W. Matolak

Faculty Publications

We introduce a test environment to replicate the well-known clustering of reflections in power delay profiles arising from late-time delays and reflections. Urban wireless propagation environments are known to exhibit such clustering. The test setup combines discrete reflections generated by a fading simulator with the continuous distribution of reflections created in a reverberation chamber. We describe measurements made in an urban environment in Denver, CO, that illustrate these multiple distributions of reflections. Our comparison of measurements made in the urban environment to those made in the new test environment shows good agreement.

Using Jackknife To Assess The Quality Of Gene Order Phylogenies, Jian Shi, Yiwei Zhang, Haiwei Luo, Jijun Tang

Faculty Publications

Background
In recent years, gene order data has attracted increasing attention from both biologists and computer scientists as a new type of data for phylogenetic analysis. If gene orders are viewed as one character with a large number of states, traditional bootstrap procedures cannot be applied. Researchers began to use a jackknife resampling method to assess the quality of gene order phylogenies.

Results
In this paper, we design and conduct a set of experiments to validate the performance of this jackknife procedure and provide discussions on how to conduct it properly. Our results show that jackknife is very useful to …

High-Performance Heterogeneous Computing With The Convey Hc-1, Jason D. Bakos

Faculty Publications

Unlike other socket-based reconfigurable coprocessors, the Convey HC-1 contains nearly 40 field-programmable gate arrays, scatter-gather memory modules, a high-capacity crossbar switch, and a fully coherent memory system.

Integrated Circuit Implementation For A Gan Hfet Driver Circuit, Bo Wang, Jason D. Bakos, Antonello Monti

Faculty Publications

This paper presents the design and implementation of a new integrated circuit (IC) that is suitable for driving the new generation of high-frequency GaN HFETs. The circuit, based upon a resonant switching transition technique, is first briefly described and then discussed in detail, focusing on the design process practical considerations. A new level-shifter topology, used to generate the zero and negative gate-source voltages required to switch the GaN HFET, is introduced and analyzed. The experimental measurements included in this paper report the results of tests carried out on an IC designed and fabricated as part of the multiproject die in …

Genome3d: A Viewer-Model Framework For Integrating And Visualizing Multi-Scale Epigenomic Information Within A Three-Dimensional Genome, Thomas M. Asbury, Matt Mitman, Jijun Tang, W. Jim Zheng

Faculty Publications

Background
New technologies are enabling the measurement of many types of genomic and epigenomic information at scales ranging from the atomic to nuclear. Much of this new data is increasingly structural in nature, and is often difficult to coordinate with other data sets. There is a legitimate need for integrating and visualizing these disparate data sets to reveal structural relationships not apparent when looking at these data in isolation.

Results
We have applied object-oriented technology to develop a downloadable visualization tool, Genome3D, for integrating and displaying epigenomic data within a prescribed three-dimensional physical model of the human genome. In order …

Phage-Induced Alignment Of Membrane Proteins Enables The Measurement And Structural Analysis Of Residual Dipolar Couplings With Dipolar Waves And Lambda-Maps, Sang Ho Park, Woo Sung Son, Rishi Mukhopadhyay, Homayoun Valafar, Stanley J. Opella

Faculty Publications

At pH > 6 added filamentous bacteriophage fd is compatible with many of the detergents used to solubilize membrane proteins for solution NMR studies of membrane proteins and, therefore, serves as an alignment media. In combination with strained polyacrylamide gel alignment, Dipolar Waves can be used to directly assess the secondary structure and a λ-map extracts the order tensors for de novo structure calculation of membrane proteins without distance restraints.

Gene Order Phylogeny And The Evolution Of Methanogens, Haiwei Luo, Zhiyi Sun, William Arndt, Jian Shi, Robert Friedman, Jijun Tang

Faculty Publications

Methanogens are a phylogenetically diverse group belonging to Euryarchaeota. Previously, phylogenetic approaches using large datasets revealed that methanogens can be grouped into two classes, “Class I” and “Class II”. However, some deep relationships were not resolved. For instance, the monophyly of “Class I” methanogens, which consist of Methanopyrales, Methanobacteriales and Methanococcales, is disputable due to weak statistical support. In this study, we use MSOAR to identify common orthologous genes from eight methanogen species and a Thermococcale species (outgroup), and apply GRAPPA and FastME to compute distance-based gene order phylogeny. The gene order phylogeny supports two classes of methanogens, but it …

Exploiting Matrix Symmetry To Improve Fpgaaccelerated Conjugate Gradient, Jason D. Bakos, Krishna K. Nagar

Faculty Publications

In this paper we describe a new approach for accelerating the Conjugate Gradient (CG) method using an FPGA co-processor. As in previous approaches, our co-processor performs a double-precision sparse matrix-vector multiplication. However, our implementation doubles the amount of computation per unit of input data by exploiting the symmetry of the input matrix and computing the upper and lower triangle of the input matrix in parallel. Using a Virtex-2 Pro 100 FPGA, we have achieved an observed computational throughput of 1155 MFLOPS.

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 …