1499375
A Fusion-Embedded Skeleton Library
This paper addresses a new framework for designing and implementing skeleton libraries, in which each skeleton should not only be efficiently implemented as is usually done, but also be equipped with a structured interface to combine it efficiently with other skeletons. We illustrate our idea with a new skeleton library for parallel programming in C++. It is simple and efficient to use just like other C++ libraries. A distinctive feature of the library is its modularity: Our optimization framework treats newly defined skeletons equally to existing ones if the interface is given. Our current experiments are encouraging, indicating that this approach is promising both theoretically and in practice.
5453797
List Homomorphism with Accumulation
This paper introduces accumulation into list homomorphisms for systematic development of both efficient and correct parallel programs. New parallelizable recursive pattern called H-homomorphism is given, and transformations from sequential patterns in the H-form and Hform into (H-)homomorphism are shown. We illustrate the power of our formalization by developing a novel and general parallel program for a class of interesting and challenging problems, known as maximum marking problems.
21046907
Construction of List Homomorphisms by Tupling and Fusion
List homomorphisms are functions which can be efficiently computed in parallel since they ideally suit the divide- sand-conquer paradigm. However, some interesting functions, e.g., the maximum segment sum problem, are not list homomorphisms. In this paper, we propose a systematic way of embedding them into list homomorphisms so that parallel programs are derived. We show, with an example, how a simple, and “obviously” correct, but possibly inefficient solution to the problem can be successfully turned into a semantically equivalent almost homomorphism by means of two transformations: tupling and fusion.
13526098
Systematic Derivation of Tree Contraction Algorithms
While tree contraction algorithms play an important role in efficient tree computation in parallel, it is difficult to develop such algorithms due to the strict conditions imposed on contracting op...
17460651
A calculational fusion system HYLO
Fusion, one of the most useful transformation tactics for deriving efficient programs, is the process whereby separate pieces of programs are fused into a single one, leading to an efficient program without intermediate data structures produced. In this paper, we report our on-going investigation on the design and implementation of an automatic transformation system HYLO which performs fusion transformation in a more systematic and more general way than any other systems. The distinguished point of our system is its calculational feature based on simple application of transformation laws rather than traditional search-based transformations.
15997088
A New Parallel Skeleton for General Accumulative Computations
Skeletal parallel programming enables programmers to build a parallel program from ready-made components (parallel primitives) for which efficient implementations are known to exist, making both the parallel program development and the parallelization process easier. Constructing efficient parallel programs is often difficult, however, due to difficulties in selecting a proper combination of parallel primitives and in implementing this combination without having unnecessary creations and exchanges of data among parallel primitives and processors. To overcome these difficulties, we propose a powerful and general parallel skeleton, accumulate, which can be used to naturally code efficient solutions to problems as well as be efficiently implemented in parallel using Message Passing Interface (MPI).
14260384
Perfect Circular Arc Coloring
The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n2m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.
471313
Dependence network modeling for biomarker identification
MOTIVATION
Our purpose is to develop a statistical modeling approach for cancer biomarker discovery and provide new insights into early cancer detection. We propose the concept of dependence network, apply it for identifying cancer biomarkers, and study the difference between the protein or gene samples from cancer and non-cancer subjects based on mass-spectrometry (MS) and microarray data.


RESULTS
Three MS and two gene microarray datasets are studied. Clear differences are observed in the dependence networks for cancer and non-cancer samples. Protein/gene features are examined three at one time through an exhaustive search. Dependence networks are constructed by binding triples identified by the eigenvalue pattern of the dependence model, and are further compared to identify cancer biomarkers. Such dependence-network-based biomarkers show much greater consistency under 10-fold cross-validation than the classification-performance-based biomarkers. Furthermore, the biological relevance of the dependence-network-based biomarkers using microarray data is discussed. The proposed scheme is shown promising for cancer diagnosis and prediction.


AVAILABILITY
See supplements: http://dsplab.eng.umd.edu/~genomics/dependencenetwork/
12036966
Literature mining and database annotation of protein phosphorylation using a rule-based system
MOTIVATION
A large volume of experimental data on protein phosphorylation is buried in the fast-growing PubMed literature. While of great value, such information is limited in databases owing to the laborious process of literature-based curation. Computational literature mining holds promise to facilitate database curation.


RESULTS
A rule-based system, RLIMS-P (Rule-based LIterature Mining System for Protein Phosphorylation), was used to extract protein phosphorylation information from MEDLINE abstracts. An annotation-tagged literature corpus developed at PIR was used to evaluate the system for finding phosphorylation papers and extracting phosphorylation objects (kinases, substrates and sites) from abstracts. RLIMS-P achieved a precision and recall of 91.4 and 96.4% for paper retrieval, and of 97.9 and 88.0% for extraction of substrates and sites. Coupling the high recall for paper retrieval and high precision for information extraction, RLIMS-P facilitates literature mining and database annotation of protein phosphorylation.
952289
DynGO: a tool for visualizing and mining of Gene Ontology and its associations
BackgroundA large volume of data and information about genes and gene products has been stored in various molecular biology databases. A major challenge for knowledge discovery using these databases is to identify related genes and gene products in disparate databases. The development of Gene Ontology (GO) as a common vocabulary for annotation allows integrated queries across multiple databases and identification of semantically related genes and gene products (i.e., genes and gene products that have similar GO annotations). Meanwhile, dozens of tools have been developed for browsing, mining or editing GO terms, their hierarchical relationships, or their "associated" genes and gene products (i.e., genes and gene products annotated with GO terms). Tools that allow users to directly search and inspect relations among all GO terms and their associated genes and gene products from multiple databases are needed.ResultsWe present a standalone package called DynGO, which provides several advanced functionalities in addition to the standard browsing capability of the official GO browsing tool (AmiGO). DynGO allows users to conduct batch retrieval of GO annotations for a list of genes and gene products, and semantic retrieval of genes and gene products sharing similar GO annotations. The result are shown in an association tree organized according to GO hierarchies and supported with many dynamic display options such as sorting tree nodes or changing orientation of the tree. For GO curators and frequent GO users, DynGO provides fast and convenient access to GO annotation data. DynGO is generally applicable to any data set where the records are annotated with GO terms, as illustrated by two examples.ConclusionWe have presented a standalone package DynGO that provides functionalities to search and browse GO and its association databases as well as several additional functions such as batch retrieval and semantic retrieval. The complete documentation and software are freely available for download from the website http://biocreative.ifsm.umbc.edu/dyngo.
53305921
Substring selection for biomedical document classification
Motivation: Attribute selection is a critical step in development of document classification systems. As a standard practice, words are stemmed and the most informative ones are used as attributes in classification. Owing to high complexity of biomedical terminology, general-purpose stemming algorithms are often conservative and could also remove informative stems. This can lead to accuracy reduction, especially when the number of labeled documents is small. To address this issue, we propose an algorithm that omits stemming and, instead, uses the most discriminative substrings as attributes. 
 
Results: The approach was tested on five annotated sets of abstracts from iProLINK that report on the experimental evidence about five types of protein post-translational modifications. The experiments showed that Naive Bayes and support vector machine classifiers perform consistently better [with area under the ROC curve (AUC) accuracy in range 0.92--0.97] when using the proposed attribute selection than when using attributes obtained by the Porter stemmer algorithm (AUC in 0.86--0.93 range). The proposed approach is particularly useful when labeled datasets are small. 
 
Contact: vucetic@ist.temple.edu 
 
Supplementary Information: The supplementary data are available from www.ist.temple.edu/PIRsupplement