Virginia Tech - Wake Forest University School of Biomedical Engineering & Sciences
Computer Science Technical Reports @Virginia TechNot a member yet
997 research outputs found
Sort by
RAxML-Cell: Parallel Phylogenetic Tree Inference on the Cell Broadband Engine
Get PDFPhylogenetic tree reconstruction is one of the grand challenge
problems in Bioinformatics. The search for a best-scoring tree with 50
organisms, under a reasonable optimality criterion, creates a
topological search space which is as large as the number of atoms in
the universe. Computational phylogeny is challenging even for the most
powerful supercomputers. It is also an ideal candidate for
benchmarking emerging multiprocessor architectures, because it
exhibits various levels of fine and coarse-grain parallelism. In this
paper, we present the porting, optimization, and evaluation of RAxML
on the Cell Broadband Engine. RAxML is a provably efficient, hill
climbing algorithm for computing phylogenetic trees based on the
Maximum Likelihood (ML) method. The algorithm uses an embarrassingly
parallel search method, which also exhibits data-level parallelism and
control parallelism in the computation of the likelihood functions.
We present the optimization of one of the currently fastest tree
search algorithms, on a real Cell blade prototype. We also
investigate problems and present solutions pertaining to the
optimization of floating point code, control flow, communication,
scheduling, and multi-level parallelization on the Cell
Semi-Supervised Learning of Hidden Markov Models via a Homotopy Method
Get PDFHidden Markov model (HMM) classifier design is considered for analysis of sequential data,
incorporating both labeled and unlabeled data for training; the balance between labeled and unlabeled
data is controlled by an allocation parameter lambda in [0, 1), where lambda = 0 corresponds to purely supervised
HMM learning (based only on the labeled data) and lambda = 1 corresponds to unsupervised HMM-based
clustering (based only on the unlabeled data). The associated estimation problem can typically be reduced
to solving a set of fixed point equations in the form of a “natural-parameter homotopyâ€. This paper
applies a homotopy method to track a continuous path of solutions, starting from a local supervised
solution (lambda = 0) to a local unsupervised solution (lambda = 1). The homotopy method is guaranteed to track
with probability one from lambda = 0 to lambda = 1 if the lambda = 0 solution is unique; this condition is not satisfied
for the HMM, since the maximum likelihood supervised solution (lambda = 0) is characterized by many local
optimal solutions. A modified form of the homotopy map for HMMs assures a track from lambda = 0 to
lambda = 1. Following this track leads to a formulation for selecting lambda in [0, 1) for a semi-supervised solution,
and it also provides a tool for selection from among multiple (local optimal) supervised solutions. The
results of applying the proposed method to measured and synthetic sequential data verify its robustness
and feasibility compared to the conventional EM approach for semi-supervised HMM training
Dynamic size and speed cursor for large, high-resolution displays
Get PDFAs larger displays become more available their lack of adequate input techniques becomes apparent. In this paper we show the scalability of the dynamic size and speed cursor for large, high-resolution displays. We introduce the idea of a dynamic paradigm for input devices, explain three implementations of the dynamic size and speed (DSS) cursor and explain results of an experiment. In our experiment we compared the three different implementations of the dynamic size and speed cursor to cursor warping and standard cursor settings. In the experiment we found gender bias for two different tasks (clicking and simple drag and drop), found that one of the dynamic size and speed cursor implementations generally outperformed cursor warping and the standard cursor setting, and explain how distance to and size of targets effected results. We conclude by suggesting the use of a dynamic size and speed cursor with large, high-resolution displays
Algorithms for Storytelling
Get PDFWe formulate a new data mining problem called "storytelling" as a generalization of redescription mining. In traditional redescription mining, we are given a set of objects and a collection of subsets defined over these objects. The goal is to view the set system as a vocabulary and identify two expressions in this vocabulary that induce the same set of objects. Storytelling, on the other hand, aims to explicitly relate object sets that are disjoint (and hence, maximally dissimilar) by finding a chain of (approximate) redescriptions between the sets. This problem finds applications in bioinformatics, for instance, where the biologist is trying to relate a set of genes expressed in one experiment to another set, implicated in a different pathway. We outline an efficient storytelling implementation that embeds the CARTwheels redescription mining algorithm in an A* search procedure, using the former to supply next move operators on search branches to the latter. This approach is practical and effective for mining large datasets and, at the same time, exploits the structure of partitions imposed by the given vocabulary. Three application case studies are presented: a study of word overlaps in large English dictionaries, exploring connections between genesets in a bioinformatics dataset, and relating publications in the PubMed index of abstracts
Finding Computer Science Syllabi on the World Wide Web
Get PDFSyllabi contain information useful to students, faculty, and many other people, and given the ubiquity of the WWW many schools are now putting their syllabi online for these people and the general public to access. Even though these syllabi may be available, they might be hard to find. This means that faculty, students, and anyone else who might have an interest in viewing those syllabi might find it useful to be able to browse a collection of reliable syllabi. To build a collection of reliable syllabi it is necessary to find those syllabi on the WWW but this is made easy with a tool like the Google Web API. Once the syllabi are found on the Web it is necessary to examine those syllabi and look for desired characteristics to be sure they are desired syllabi. The syllabi that contain the desired characteristics are kept and the rest are discarded. This elimination process can be accomplished using a tool like a classification tree, more specifically, tools like the Orange Data Mining Library and C4.5. This paper describes the process of finding syllabi on the WWW using the Google Web API, retrieving those syllabi using Python, and filtering them using the Orange Data Mining Library and C4.5 so that a reliable set of syllabi can be constructed
The Challenges of Web Engineering and Requirements for Better Tool Support
Get PDFWe report the experiences of semi-professional developers regarding the challenges, tools, and processes within the domain of web application development. The paper summarizes the main problems in web development, characterizes the habits of programmers and concludes with a "developer's wish list" for improvements to web technologies and tools. The report is based on two independent sources - a survey of 31 web developers and an in-depth interview study with 10 participants
A problem solving environment for the wood-based composites industry
Get PDFProduct quality and cost efficiency continue to grow in importance for the wood-based
composites industry. The complex dynamics of the manufacturing process lends itself to the
adoption of simulation models. Simulation models may be used to understand and manipulate the many parameters involved in the manufacturing process. However, most of the simulation
models that have been developed over the last two decades have not been implemented due to a lack of continued technical support and a poor user interface. WBCSim is a prototype, Web based, problem solving environment (PSE) that was developed to assist manufacturers and
scientists in the design and manufacture of selected wood-based composite products. At the heart of WBCSim is a collection of legacy codes, which are described here. This PSE demonstrates the possibility of implementing scientific computing into a manufacturing application
EtanaViz: A Visual User Interface to Archaeological Digital Libraries
Get PDFAnalyzing and hypothesizing are important scientific processes involved in archaeological activity. In this paper, we describe a visual user interface closely coupled with services for archaeological digital libraries, to help archaeologists analyze data and test hypotheses. Our system, EtanaViz, employs a dynamic hyperbolic tree to display hierarchical relationships among excavation records, based on spatial, temporal, and artifact-related taxonomies. Also, EtanaViz provides stacked bar charts to indicate categories. More specifically, we show how EtanaViz can help users analyze data about animal bones excavated from two archaeological sites, Tell Nimrin and Tell al-'Umayri'. The fauna are associated with cultural phases. Comparisons of animal bones from Tell Nimrin across cultural phases provide insights into changing subsistence strategies during these time periods. Inter-site comparisons also show shifts in animal use as well as long-term adaptations to environmental changes
Schema Mapper: A Visualization Tool for DL Integration
Get PDFSchema mapping is a challenging problem. It has come to the fore in recent years; there are important applications like database schema integration and, more recently, digital library merging of heterogeneous data. Previous studies have approached the schema mapping process either from algorithmic or visualization perspectives, with few integrating both. With Schema Mapper we demonstrate a semi-automatic tool for schema integration that combines a novel visual interface with an algorithm-based recommendation engine. Schemas are visualized as hyperbolic trees (see Fig. 1), thus allowing more schema nodes to be displayed at one time. Matches to selections are recommended to the user, which makes the mapping operation easier and faster
SchemaMapper: A tool for visualization of schema mapping
Get PDFThe world has changed significantly in the past few years with an increasing thrust towards the use of digital information. Every kind of application domain has found reasons to use digital information sources extensively. As a result, different types of data representation models or schemas have been developed. This poses a problem when there is a need for data integration from several sources. Diverse representations must be merged in order to create a single global representation. Hence there is a need for schema mapping tools that will enable amalgamation of heterogeneous data representations. That goal is difficult to achieve today since existing schema mapping tools are domain unaware. SchemaMapper, a new tool we have developed, tries to be domain aware and hence help speed up the schema mapping process. Further, it supports visualization of the mapping process by using a hyperbolic tree representation. This has not been used before in the context of schema mapping. Although the primary motivation for SchemaMapper comes from ETANA-DL (a digital library to promote integration of information and services from diverse archaeological sites), it can potentially be used in any other similar domains in the future, or further extended for different types of schema mappings. This report describes in detail the prototype developed for exploring the feasibility of such a tool, providing architecture and implementation details. Experiments were conducted to evaluate SchemaMapper and the initial results have been very encouraging. All the schemas used during the evaluation process were real life examples taken from ETANA-DL. Analysis of the evaluation results suggests that domain awareness is extremely useful for the schema mapping process. Also, the linear tree representation of schemas which existing tools use appears to have inherent disadvantages which need to be overcome in order to make the process more effective