38460463
Formal derivation of efficient parallel programs by construction of list homomorphisms
It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad hoc in the development of efficient parallel programs. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and “obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism.” The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.
9579545
An Injective Language for Reversible Computation
Erasure of information incurs an increase in entropy and dissipates heat. Therefore, information-preserving computation is essential for constructing computers that use energy more effectively. A more recent motivation to understand reversible transformations also comes from the design of editors where editing actions on a view need to be reflected back to the source data. In this paper we present a point-free functional language, with a relational semantics, in which the programmer is allowed to define injective functions only. Non-injective functions can be transformed into a program returning a history. The language is presented with many examples, and its relationship with Bennett’s reversible Turing machine is explained. The language serves as a good model for program construction and reasoning for reversible computers, and hopefully for modelling bi-directional updating in an editor.
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...
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).
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.
11184766
Swapping Arguments and Results of Recursive Functions
Many useful calculation rules, such as fusion and tupling, rely on well-structured functions, especially in terms of inputs and outputs. For instance, fusion requires that well-produced outputs should be connected to well-consumed inputs, so that unnecessary intermediate data structures can be eliminated. These calculation rules generally fail to work unless functions are well-structured. In this paper, we propose a new calculation rule called IO swapping. IO swapping exchanges call-time computations (occurring in the arguments) and return-time computations (occurring in the results) of a function, while guaranteeing that the original and resulting function compute the same value. IO swapping enables us to rearrange inputs and outputs so that the existing calculation rules can be applied. We present new systematic derivations of efficient programs for detecting palindromes, and a method of higher-order removal that can be applied to defunctionalize function arguments, as two concrete applications.
7795322
The Protein Information Resource
The Protein Information Resource (PIR) is an integrated public resource of protein informatics that supports genomic and proteomic research and scientific discovery. PIR maintains the Protein Sequence Database (PSD), an annotated protein database containing over 283 000 sequences covering the entire taxonomic range. Family classification is used for sensitive identification, consistent annotation, and detection of annotation errors. The superfamily curation defines signature domain architecture and categorizes memberships to improve automated classification. To increase the amount of experimental annotation, the PIR has developed a bibliography system for literature searching, mapping, and user submission, and has conducted retrospective attribution of citations for experimental features. PIR also maintains NREF, a non-redundant reference database, and iProClass, an integrated database of protein family, function, and structure information. PIR-NREF provides a timely and comprehensive collection of protein sequences, currently consisting of more than 1 000 000 entries from PIR-PSD, SWISS-PROT, TrEMBL, RefSeq, GenPept, and PDB. The PIR web site (http://pir.georgetown.edu) connects data analysis tools to underlying databases for information retrieval and knowledge discovery, with functionalities for interactive queries, combinations of sequence and text searches, and sorting and visual exploration of search results. The FTP site provides free download for PSD and NREF biweekly releases and auxiliary databases and files.
12615323
PIRSF: family classification system at the Protein Information Resource
The Protein Information Resource (PIR) is an integrated public resource of protein informatics. To facilitate the sensible propagation and standardization of protein annotation and the systematic detection of annotation errors, PIR has extended its superfamily concept and developed the SuperFamily (PIRSF) classification system. Based on the evolutionary relationships of whole proteins, this classification system allows annotation of both specific biological and generic biochemical functions. The system adopts a network structure for protein classification from superfamily to subfamily levels. Protein family members are homologous (sharing common ancestry) and homeomorphic (sharing full-length sequence similarity with common domain architecture). The PIRSF database consists of two data sets, preliminary clusters and curated families. The curated families include family name, protein membership, parent-child relationship, domain architecture, and optional description and bibliography. PIRSF is accessible from the website at http://pir.georgetown.edu/pirsf/ for report retrieval and sequence classification. The report presents family annotation, membership statistics, cross-references to other databases, graphical display of domain architecture, and links to multiple sequence alignments and phylogenetic trees for curated families. PIRSF can be utilized to analyze phylogenetic profiles, to reveal functional convergence and divergence, and to identify interesting relationships between homeomorphic families, domains and structural classes.
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/
38894685
A Strongly Polynomial Algorithm for the Inverse Shortest Arborescence Problem
Abstract In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given v1 -arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n3) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem.