A growing body of knowledge about biological mechanisms and interaction of biological components is contained in the peer-reviewed scientific literature. In order to leverage this knowledge towards the development of predictive models, one must first extract these relationships from the text. However, the context in which the interaction was reported is critical in ensuring that it is used in a manner consistent with the model's intended application. Here we assess the applicability of two generic automated methods for leveraging a broader contextual structure in the more specific domain of a biological experiment using only the paper's title and abstract. In an example use case, a Support Vector Machine (SVM) and two variants of the broadly-used Bidirectional Encoder Representations from Transformers (BERT) neural network model, serve to distinguish mouse from human subject experiments in a corpus of over 12,000 papers documenting mechanistic interactions in a regulatory model of of mucosal immune signaling. The BERT and domain-specific BioBERT yielded essentially equivalent classification accuracy with both neural network models performing only marginally better than the SVM. Words occurring frequently in abstracts were largely non-specific, whereas words unique to each class were used in 4% or less of the abstracts. These high-specificity words were used in very similar contexts that separated mouse and human study abstracts on the basis of study design and experimental procedure rather than species or basic biological markers.

Codon bias, the usage patterns of synonymous codons for encoding a protein sequence as nucleotides, is a biological phenomenon that is not fully understood. Several methods exist to represent the codon bias of an organism: codon adaptation index (CAI) [1], individual codon usage (ICU), hidden stop codons (HSC) [2] and codon context (CC) [3]. These methods are often employed in the optimization of heterologous gene expression to increase the accuracy and rate of translation. They, however, have many shortcomings as they dont take into account the local and global context of a gene. We present a method for modeling global and local codon bias through deep language models that is more robust than current methods by providing more contextual information and long-range dependencies.

Comparing genomes to identify polymorphisms is a difficult task, especially beyond single nucleotide poly-morphisms. Polymorphism detection is important in disease association studies as well as in phylogenetic tree reconstruc-tion. We present a method for identifying polymorphisms in genomes by using a modified version de Bruijn graphs, data structures widely used in genome assembly from Next-Generation Sequencing. Using our method, we are able to identify polymorphisms that exist within a genome as well as well as see graph structures that form in the de Bruijn graph for particular types of polymorphisms (translocations, etc.).

We present kleuren, a novel assembly-free method to reconstruct phylogenetic trees using the Colored de Bruijn Graph. kleuren works by constructing the Colored de Bruijn Graph and then traversing it, finding bubble structures in the graph that provide phylogenetic signal. The bubbles are then aligned and concatenated to form a supermatrix, from which a phylogenetic tree is inferred. We introduce the algorithms that kleuren uses to accomplish this task, and show its performance on reconstructing the phylogenetic tree of 12 Drosophila species. kleuren reconstructed the established phylogenetic tree accurately, and is a viable tool for phylogenetic tree reconstruction using whole genome sequences. Software package available at: https://github.com/Colelyman/kleuren.

Detecting homologous sequences in organisms is an essential step in protein structure and function prediction, gene annotation and phylogenetic tree construction. Heuristic methods are often employed for quality control of putative homology clusters. These heuristics, however, usually only apply to pairwise sequence comparison and do not examine clusters as a whole. We present the Orthology Group Cleaner (the OGCleaner), a tool designed for filtering putative orthology groups as homology or non-homology clusters by considering all sequences in a cluster. The OGCleaner relies on high-quality orthologous groups identified in OrthoDB to train machine learning algorithms that are able to distinguish between true-positive and false-positive homology groups. This package aims to improve the quality of phylogenetic tree construction especially in instances of lower-quality transcriptome assemblies. AVAILABILITY AND IMPLEMENTATION: https://github.com/byucsl/ogcleaner CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

MOTIVATION: The contig orientation problem, which we formally define as the MAX-DIR problem, has at times been addressed cursorily and at times using various heuristics. In setting forth a linear-time reduction from the MAX-CUT problem to the MAX-DIR problem, we prove the latter is NP-complete. We compare the relative performance of a novel greedy approach with several other heuristic solutions. RESULTS: Our results suggest that our greedy heuristic algorithm not only works well but also outperforms the other algorithms due to the nature of scaffold graphs. Our results also demonstrate a novel method for identifying inverted repeats and inversion variants, both of which contradict the basic single-orientation assumption. Such inversions have previously been noted as being difficult to detect and are directly involved in the genetic mechanisms of several diseases. AVAILABILITY AND IMPLEMENTATION: http://bioresearch.byu.edu/scaffoldscaffolder. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Genome-wide association studies (GWAS) have effectively identified genetic factors for many diseases. Many diseases, including Alzheimer's disease (AD), have epistatic causes, requiring more sophisticated analyses to identify groups of variants which together affect phenotype. RESULTS: Based on the GWAS statistical model, we developed a multi-SNP GWAS analysis to identify pairs of variants whose common occurrence signaled the Alzheimer's disease phenotype. CONCLUSIONS: Despite not having sufficient data to demonstrate significance, our preliminary experimentation identified a high correlation between GRIA3 and HLA-DRB5 (an AD gene). GRIA3 has not been previously reported in association with AD, but is known to play a role in learning and memory.

BACKGROUND: Accurate detection of homologous relationships of biological sequences (DNA or amino acid) amongst organisms is an important and often difficult task that is essential to various evolutionary studies, ranging from building phylogenies to predicting functional gene annotations. There are many existing heuristic tools, most commonly based on bidirectional BLAST searches that are used to identify homologous genes and combine them into two fundamentally distinct classes: orthologs and paralogs. Due to only using heuristic filtering based on significance score cutoffs and having no cluster post-processing tools available, these methods can often produce multiple clusters constituting unrelated (non-homologous) sequences. Therefore sequencing data extracted from incomplete genome/transcriptome assemblies originated from low coverage sequencing or produced by de novo processes without a reference genome are susceptible to high false positive rates of homology detection. RESULTS: In this paper we develop biologically informative features that can be extracted from multiple sequence alignments of putative homologous genes (orthologs and paralogs) and further utilized in context of guided experimentation to verify false positive outcomes. We demonstrate that our machine learning method trained on both known homology clusters obtained from OrthoDB and randomly generated sequence alignments (non-homologs), successfully determines apparent false positives inferred by heuristic algorithms especially among proteomes recovered from low-coverage RNA-seq data. Almost ~42 % and ~25 % of predicted putative homologies by InParanoid and HaMStR respectively were classified as false positives on experimental data set. CONCLUSIONS: Our process increases the quality of output from other clustering algorithms by providing a novel post-processing method that is both fast and efficient at removing low quality clusters of putative homologous genes recovered by heuristic-based approaches.

BACKGROUND: Genome assemblers to date have predominantly targeted haploid reference reconstruction from homozygous data. When applied to diploid genome assembly, these assemblers perform poorly, owing to the violation of assumptions during both the contigging and scaffolding phases. Effective tools to overcome these problems are in growing demand. Increasing parameter stringency during contigging is an effective solution to obtaining haplotype-specific contigs; however, effective algorithms for scaffolding such contigs are lacking. METHODS: We present a stand-alone scaffolding algorithm, ScaffoldScaffolder, designed specifically for scaffolding diploid genomes. The algorithm identifies homologous sequences as found in "bubble" structures in scaffold graphs. Machine learning classification is used to then classify sequences in partial bubbles as homologous or non-homologous sequences prior to reconstructing haplotype-specific scaffolds. We define four new metrics for assessing diploid scaffolding accuracy: contig sequencing depth, contig homogeneity, phase group homogeneity, and heterogeneity between phase groups. RESULTS: We demonstrate the viability of using bubbles to identify heterozygous homologous contigs, which we term homolotigs. We show that machine learning classification trained on these homolotig pairs can be used effectively for identifying homologous sequences elsewhere in the data with high precision (assuming error-free reads). CONCLUSION: More work is required to comparatively analyze this approach on real data with various parameters and classifiers against other diploid genome assembly methods. However, the initial results of ScaffoldScaffolder supply validity to the idea of employing machine learning in the difficult task of diploid genome assembly. Software is available at http://bioresearch.byu.edu/scaffoldscaffolder.

BACKGROUND: Error correction is an important step in increasing the quality of next-generation sequencing data for downstream analysis and use. Polymorphic datasets are a challenge for many bioinformatic software packages that are designed for or assume homozygosity of an input dataset. This assumption ignores the true genomic composition of many organisms that are diploid or polyploid. In this survey, two different error correction packages, Quake and ECHO, are examined to see how they perform on next-generation sequence data from heterozygous genomes. RESULTS: Quake and ECHO perform well and were able to correct many errors found within the data. However, errors that occur at heterozygous positions had unique trends. Errors at these positions were sometimes corrected incorrectly, introducing errors into the dataset with the possibility of creating a chimeric read. Quake was much less likely to create chimeric reads. Quake's read trimming removed a large portion of the original data and often left reads with few heterozygous markers. ECHO resulted in more chimeric reads and introduced more errors than Quake but preserved heterozygous markers. CONCLUSIONS: These findings suggest that Quake and ECHO both have strengths and weaknesses when applied to heterozygous data. With the increased interest in haplotype specific analysis, new tools that are designed to be haplotype-aware are necessary that do not have the weaknesses of Quake and ECHO.

Moleculo DNA sequencing technology provides extremely accurate, phased, reads having an average length of over 4,000 bp. Very little is yet known about the precise characteristics of these reads. We estimate a lower bound for the single nucleotide substitution error rate of these reads, and provide probabilities for each type of substitution. We also present preliminary work on the development of an error correction algorithm for these reads which in its current implementation corrects 74,030 single nucleotide errors in a Moleculo data set obtained from Rubus idaeus `Heritage'. We also demonstrate that the pattern of substitution errors shows no significant bias with respect to the position of an error along the body of a read.

Secondary structure prediction is an important step in understanding gene function. Several algorithms have been proposed for applying machine learning techniques to this problem. This research examines these algorithms and constructs a framework that is effective in providing accurate predictions.

BACKGROUND: DNA methylation has been linked to many important biological phenomena. Researchers have recently begun to sequence bisulfite treated DNA to determine its pattern of methylation. However, sequencing reads from bisulfite-converted DNA can vary significantly from the reference genome because of incomplete bisulfite conversion, genome variation, sequencing errors, and poor quality bases. Therefore, it is often difficult to align reads to the correct locations in the reference genome. Furthermore, bisulfite sequencing experiments have the additional complexity of having to estimate the DNA methylation levels within the sample. RESULTS: Here, we present a highly accurate probabilistic algorithm, which is an extension of the Genomic Next-generation Universal MAPper to accommodate bisulfite sequencing data (GNUMAP-bs), that addresses the computational problems associated with aligning bisulfite sequencing data to a reference genome. GNUMAP-bs integrates uncertainty from read and mapping qualities to help resolve the difference between poor quality bases and the ambiguity inherent in bisulfite conversion. We tested GNUMAP-bs and other commonly-used bisulfite alignment methods using both simulated and real bisulfite reads and found that GNUMAP-bs and other dynamic programming methods were more accurate than the more heuristic methods. CONCLUSIONS: The GNUMAP-bs aligner is a highly accurate alignment approach for processing the data from bisulfite sequencing experiments. The GNUMAP-bs algorithm is freely available for download at: http://dna.cs.byu.edu/gnumap. The software runs on multiple threads and multiple processors to increase the alignment speed.

BACKGROUND: Since the advent of microarray technology, numerous methods have been devised to infer gene regulatory relationships from gene expression data. Many approaches that infer entire regulatory networks. This produces results that are rich in information and yet so complex that they are often of limited usefulness for researchers. One alternative unit of regulatory interactions is a linear path between genes. Linear paths are more comprehensible than networks and still contain important information. Such paths can be extracted from inferred regulatory networks or inferred directly. Since criteria for inferring networks generally differs from criteria for inferring paths, indirect and direct inference of paths may achieve different results. RESULTS: This paper explores a strategy to infer linear pathways by converting the path inference problem into a shortest-path problem. The edge weights used are the negative log-transformed probabilities of directness derived from the posterior joint distributions of pairwise mutual information between gene expression levels. Directness is inferred using the data processing inequality. The method was designed with two goals. One is to achieve better accuracy in path inference than extraction of paths from inferred networks. The other is to facilitate priorization of interactions for laboratory validation. A method is proposed for achieving this by ranking paths according to the joint probability of directness of each path's edges. The algorithm is evaluated using simulated expression data and is compared to extraction of shortest paths from networks inferred by two alternative methods, ARACNe and a minimum spanning tree algorithm. CONCLUSIONS: Direct path inference appears to achieve accuracy competitive with that obtained by extracting paths from networks inferred by the other methods. Preliminary exploration of the use of joint edge probabilities to rank paths is largely inconclusive. Suggestions for a better framework for such comparisons are discussed.

BACKGROUND: Recent advances in sequencing technology have created large data sets upon which phylogenetic inference can be performed. Current research is limited by the prohibitive time necessary to perform tree search on a reasonable number of individuals. This research develops new phylogenetic algorithms that can operate on tens of thousands of species in a reasonable amount of time through several innovative search techniques. RESULTS: When compared to popular phylogenetic search algorithms, better trees are found much more quickly for large data sets. These algorithms are incorporated in the PSODA application available at http://dna.cs.byu.edu/psoda CONCLUSIONS: The use of Partial Tree Mixing in a partition based tree space allows the algorithm to quickly converge on near optimal tree regions. These regions can then be searched in a methodical way to determine the overall optimal phylogenetic solution.

SUMMARY: Many online sources of gene interaction networks supply rich visual data regarding gene pathways that can aid in the study of biological processes, disease research and drug discovery. PathGen incorporates data from several sources to create transitive connections that span multiple gene interaction databases. Results are displayed in a comprehensible graphical format, showing gene interaction type and strength, database source and microarray expression data. These features make PathGen a valuable tool for in silico discovery of novel gene interaction pathways, which can be experimentally tested and verified. The usefulness of PathGen interaction analyses was validated using genes connected to the altered facial development related to Down syndrome. AVAILABILITY: http://dna.cs.byu.edu/pathgen. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. Further information is available at http://dna.cs.byu.edu/pathgen/PathGenSupplemental.pdf.

MOTIVATION: The advent of next-generation sequencing technologies has increased the accuracy and quantity of sequence data, opening the door to greater opportunities in genomic research. RESULTS: In this article, we present GNUMAP (Genomic Next-generation Universal MAPper), a program capable of overcoming two major obstacles in the mapping of reads from next-generation sequencing runs. First, we have created an algorithm that probabilistically maps reads to repeat regions in the genome on a quantitative basis. Second, we have developed a probabilistic Needleman-Wunsch algorithm which utilizes _prb.txt and _int.txt files produced in the Solexa/Illumina pipeline to improve the mapping accuracy for lower quality reads and increase the amount of usable data produced in a given experiment. AVAILABILITY: The source code for the software can be downloaded from http://dna.cs.byu.edu/gnumap.

We present a new algorithm, ChemAlign, that uses physicochemical properties and secondary structure elements to create biologically relevant multiple sequence alignments (MSAs). Additionally, we introduce the physicochemical property difference (PPD) score for the evaluation of MSAs. This score is the normalized difference of physicochemical property values between a calculated and a reference alignment. It takes a step beyond sequence similarity and measures characteristics of the amino acids to provide a more biologically relevant metric. ChemAlign is able to produce more biologically correct alignments and can help to identify potential drug docking sites.

The performance of maximum likelihood searches can be boosted by using the most parsimonious tree as a starting point for the search. The time spent in performing the parsimony search to find this starting tree is insignificant compared to the time spent in the maximum likelihood search, leading to an overall gain in search time. These parsimony boosted maximum likelihood searches lead to topologies with scores statistically similar to the unboosted searches, but in less time.

The relationship between changes in gene expression and physical characteristics associated with Down syndrome is not well understood. Chromosome 21 genes interact with nonchromosome 21 genes to produce Down syndrome characteristics. This indirect influence, however, is difficult to empirically define due to the number, size, and complexity of the involved gene regulatory networks. This work links chromosome 21 genes to non-chromosome 21 genes known to interact in a Down syndrome phenotype through a reachability analysis of labeled transition graphs extracted from published gene regulatory network databases. The analysis provides new relations in a recently discovered link between a specific gene and Down syndrome phenotype. This type of formal analysis helps scientists direct empirical studies to unravel chromosome 21 gene interactions with the hope for therapeutic intervention.

Abstract Motivation: Multiple sequence alignments (MSAs) are at the heart of bioinformatics analysis. Recently, a number of multiple protein sequence alignment benchmarks (i.e. BAliBASE, OXBench, PREFAB and SMART) have been released to evaluate new and existing MSA applications. These databases have been well received by researchers and help to quantitatively evaluate MSA programs on protein sequences. Unfortunately, analogous DNA benchmarks are not available, making evaluation of MSA programs difficult for DNA sequences. Results: This work presents the first known multiple DNA sequence alignment benchmarks that are (1) comprised of protein-coding portions of DNA (2) based on biological features such as the tertiary structure of encoded proteins. These reference DNA databases contain a total of 3545 alignments, comprising of 68 581 sequences. Two versions of the database are available: mdsa_100s and mdsa_all. The mdsa_100s version contains the alignments of the data sets that TBLASTN found 100% sequence identity for each sequence. The mdsa_all version includes all hits with an E-value score above the threshold of 0.001. A primary use of these databases is to benchmark the performance of MSA applications on DNA data sets. The first such case study is included in the Supplementary Material. Availability: The databases, further details and the Supplementary Material are publicly available at http://csl.cs.byu.edu/mdsas/http://csl.cs.byu.edu/mdsas/ Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

DNA sequence alignment is a critical step in identifying homology between organism. The most widely used alignment program, ClustalW is known to suffer from the local minima problem, where suboptimal guide trees produce incorrect gap insertions. The optimization alignment approach, has been shown to be effective in combining alignment and phylogenetic search in order to avoid the problems associated with poor guide trees. The optimization alignment algorithm operates at a small grain size, aligning each tree found, wasting time producing multiple sequence alignments for suboptimal trees. This research develops and analyzes a large grain size algorithm for optimization alignment that iterates through steps of alignment and phylogeny search, thus improving the quality of guide trees used for computation of multiple sequence alignments and eliminating computation of multiple sequence alignments for sub-optimal guide trees. Local minima are avoided by the use of stochastic search methods. Large Grain Size Stochastic Optimization Alignment (LGA) exploits the relationship between phylogenies and multiple sequence alignments, and in so doing achieves improved alignment accuracy. LGA is licensed under the GNU General Public License. Source code and data sets are publicly available at http://csl.cs.byu.edu/lga/

The Internet is comprised of vast networks of wires and fiber. A common misconception is that there is an unlimited amount of bandwidth; in reality there exists only a finite amount. Each length of wire and fiber is owned by a company, and every company wants to maximize its profit. One means of improving profit is to overbook existing transmission lines in order to increase income without increasing expenses. If too much overbooking is performed, the quality of service (QoS) seen by customers declines. This paper explains a process to achieve an optimal overbooking ratio (OR) for admission control in network routers. By optimizing the overbooking ratio, profits can be increased while minimizing QoS problems for users.

As the Internet began its exponential growth into a global information environment, software was often unreliable, slow and had difficulty in interoperating with other systems. Supercomputing node counts also continue to follow high growth trends. Supercomputer and grid resource management software must mature into a reliable computational platform in much the same way that web services matured for the Internet. DOGMA The Next Generation (DOGMA-NG) improves on current resource management approaches by using tested off-the-shelf enterprise technologies to build a robust, scalable, and extensible resource management platform. Distributed web service technologies constitute the core of DOGMA-NG's design and provide fault tolerance and scalability. DOGMA-NG's use of open standard web technologies and efficient management algorithms promises to reduce management time and accommodate the growing size of future supercomputers. The use of web technologies also provides the opportunity for anew parallel programming paradigm, enterprise web services parallel programming, that also gains benefit from the scalable, robust component architecture.

Meta-scheduling, a process which allows a user to schedule a job across multiple sites, has a potential for livelock. Current systems avoid livelock by locking down resources at multiple sites and allowing a meta-scheduler to control the resources during the lock down period or by limiting job size to that which will fit on one site. The former approach leads to poor utilization; the later poses limitations on job size. This research uses BYU's Meta-scheduler (YMS) which allows jobs to be scheduled across multiple sites without the need for locking down the nodes. YMS avoids livelock through exponential back-off. This research quantifies the potential for livelock, determines a suitable back-off period, and provides a structure upon which to test theoretical local schedulers. The results show that livelock exists and that a suitable exponential back-off not only avoids livelock but reduces the scheduling time for each job.

As Internet usage proliferates, resource security becomes both more important and more complex. Contemporary users and systems are ill-equipped to deal with the complex security demands of a ubiquitous, insecure network. The YGuard Access Control Model, developed at Brigham Young University, employs set-based access control lists, XML, and a modular architecture to provide users with an intuitive, extensible, and efficient method of controlling access to system resources. The implementation of YGuard in XWeb, a research project designed to replace HTTP, demonstrates the power and flexibility of the model and its potential for use in diverse modern systems. This paper examines the effectiveness of the YGuard Access Control Model in solving many of the access control problems associated with the modern, networked computing environment.

Heterogeneous parallel clusters of workstations are being used to solve many important computational problems. Scheduling parallel applications on the best collection of machines in a heterogeneous computing environment is a complex problem. Performance prediction is vital to good application performance in this environment since utilization of an ill-suited machine can slow the computation down significantly. The heterogeneity of the different pieces composing the parallel platform (network links, CPU, memory, and OS) makes it incredibly difficult to accurately predict performance. This paper addresses the problem of network performance prediction. Since communication speed is often the bottleneck for parallel application perfomance, network performance prediction is important to the overall performance prediction problem. A new methodology for characterizing network links and application's need for network resources is developed which makes use of performance surfaces (Clement et al., 1998). Mathematical operations on the performance surfaces are introduced that calculate an application's affinity for a network configuration. These affinity measures can be used for the scheduling of parallel applications.

Recent advances in DNA sequencing technology have created large data sets upon which phylogenetic inference can be performed. However, current research is limited by the prohibitive time necessary to perform tree search on even a reasonably sized data set. Some parallel algorithms have been developed but the biological research community does not use them because they don’t trust the results from newly developed parallel software. This paper presents a new phylogenetic algorithm that allows existing, trusted phylogenetic software packages to be executed in parallel using the DOGMA parallel processing system. The results presented here indicate that data sets that currently take as much as 11 months to search using current algorithms, can be searched in as little as 2 hours using as few as 8 processors. This reduction in the time necessary to complete a phylogenetic search allows new research questions to be explored in many of the biological sciences.

CORBA applications can transparently use service instances running on the client's machine, on the local-area network, or across the Internet. Standard CORBA services help the application locate service instances, but do not provide a mechanism to identify service instances that will give good performance. The PerformanceBroker executes performance test suites on application service instances and selects service instances that will give superior application performance. The Broker weights performance test results according to client-specified criteria to choose the service instances that will provide the best application performance and allocates those service instances to clients. Tests with a distributed ray tracing application show that service instances chosen by the PerformanceBroker give better performance than service instances chosen by round-robin or random selection in local-area network and Internet environments.

Phylogenetic analysis is an integral part of many biological research programs. In essence, it is the study of gene genealogy. It is the study of gene mutation and the generational relationships. Phylogenetic analysis is being used in many diverse areas such as human epidemiology, viral transmission, biogeography, and systematics. Researchers are now commonly generating many DNA sequences from many individuals, thus creating very large data sets. However, our ability to analyze the data has not kept pace with data generation, and phylogenetics has now reached a crossroads where we cannot effectively analyze the data we generate. The chief challenge of phylogenetic systematics in the next century will be to develop algorithms and search strategies to effectively analyze large data sets. The crux of the computational problem is that the actual landscape of possible topologies can be extraordinarily difficult to evaluate with large data sets. The parsimony ratchet is actually a family of iterative tree search methods that use a statistical approach to sampling tree islands and ultimately finding the most parsimonious trees for a data set. Each iteration of the parsimony ratchet may occur in parallel as there is no direct dependency between iterations. The authors' implementation of the parallel ratchet is masterworker based. A master process is launched in the DOGMA system which then launches worker tasks on available nodes. Each worker task is simply wrapper code that is used to interact with the newest release version of NONA.

Heterogeneous distributed computing has traditionally been a problematic undertaking which increases in complexity as heterogeneity increases. The recent advent of Java has made heterogeneous computing a fairly straightforward task. Nevertheless, many researchers have not considered the use of Java in a mainstream parallel programming environment. The performance of Java just-in-time compilers currently approaches optimized C for many applications, making Java a serious contender for supercomputing application development. This paper presents DOGMA (Distributed Object Group Metacomputing Architecture)-a new Java-based system which enables parallel computing on heterogeneous computers. DOGMA provides support for dedicated clusters as well as idle workstations through the use of a Web-based browse-in feature or the DOGMA screen saver, which improves workstation utilization. DOGMA supports parallel programming in both a traditional message-passing form and a novel object-oriented approach. This research provides a unified environment for developing high-performance supercomputing applications on heterogeneous systems.

The performance of Java just-in-time compilers currently approaches native C++, making Java a serious contender for supercomputing application development. This paper presents DOGMA – a new Java based system which enables parallel computing on heterogeneous computers. DOGMA supports parallel programming in both a traditional message-passing form and a novel object-oriented approach. DOGMA provides support for dedicated clusters as well as idle workstations through the use of a web-based browse-in feature or the DOGMA screen saver. This research provides a unified environment for developing high-performance supercomputing applications on heterogeneous systems. © 1998 John Wiley & Sons, Ltd.

An important development in cluster computing is the availability of multiprocessor workstations. These are able to provide additional computational power to the cluster without increasing network overhead and allow multiparadigm parallelism, which we define to be the simultaneous application of both distributed and shared memory parallel processing techniques to a single problem. In this paper we compare execution times and speedup of parallel programs written in a pure message-passing paradigm with those that combine message passing and shared-memory primitives in the same application. We consider three basic applications that are common building blocks for many scientific and engineering problems: numerical integration, matrix multiplication and Jacobi iteration. Our results indicate that the added complexity of combining shared- and distributed-memory programming methods in the same program does not contribute sufficiently to performance to justify the added programming complexity.

Music synthesis often relies on very computationally intensive algorithms. Various strategies have been used to deal with the complexity, including using simpler, but more limited algorithms, using specialized hardware, and executing them in non-real-time for later playback. Although several implementations using parallel hardware have been done, very little has been done with distributed implementations on clusters of workstations. Distributed music synthesis is typical of distributed multimedia applications which use multiple servers to do computations generating high-bandwidth audio/video data, based on low-bandwidth control information. This work demonstrates distributed music synthesis and describes the effects of using different communication protocols and networks. The implementation is a version of the Csound music synthesis package which has been modified to distribute the synthesis load to multiple servers. The network performance should also be applicable to applications which use a high-bandwidth pipeline of processes, which would be appropriate for audio and video post-processing.

The paper describes initial findings regarding the performance tradeoffs between cluster computing where the participating processors are independent machines connected by a high speed switch and desktop multiprocessing where the processors reside within a single workstation and share a common memory. While interprocessor communication time has typically been cited as the limiting force on performance in the cluster, bus and memory contention have had similar effects in shared memory systems. The advent of high speed interconnects and improved bus and memory access speeds have enhanced the performance curves of both platforms. We present comparisons of the execution times of three applications with varying levels of data dependencies-numerical integration, matrix multiplication, and Jacobi iteration across three environments: the PVM distributed memory model, the PVM shared memory model, and the Solaris threads package.

The advantages of workstation clusters as a parallel computing platform include a superior price-performance ratio, availability, scalability, and ease of incremental growth. However, the performance of traditional LAN technologies such as Ethernet and FDDI rings are insufficient for many parallel applications. This paper describes APACHE (Automated Pvm Application CHaracterization Environment), an automated analysis system that uses an application-independent model for predicting the impact of ATM on the execution time of iterative parallel applications. APACHE has been used to predict the performance of several core applications that form the basis for many real scientific and engineering problems. We present a comparison of the performance predicted by APACHE with observed execution times to demonstrate the accuracy of our model. Finally, we present a method for a simple cost-benefit analysis that can be used to determine whether an investment in ATM equipment is justified for a particular workstation cluster environment.

Multicomputers have the potential to deliver Gigaflop performance on many scientific applications. Initial implementations of parallel programs on these machines, however, are often inefficient and require significant optimization before they can harness the potential power of the machine. Performance prediction tools can provide valuable information on which optimizations will result in increased performance. This paper describes an analytical performance prediction model. The model is designed to provide performance data to compilers, programmers and system architects to assist them in making choices which will lead to more efficient implementations. Efficient performance prediction tools can provide information which will help programmers make better use of the power of multicomputers. 1 Introduction One of the most important advances in high performance computing is the increasing availability of commercial parallel computers. These machines promise to provide solutions to many p...