BACKGROUND: Next-generation sequencing technologies revolutionized genomics by producing high-throughput reads at low cost, and this progress has prompted the recent development of de novo assemblers. Multiple assembly methods based on de Bruijn graph have been shown to be efficient for Illumina reads. However, the sequencing errors generated by the sequencer complicate analysis of de novo assembly and influence the quality of downstream genomic researches. RESULTS: In this paper, we develop a de Bruijn assembler, called Clover (clustering-oriented de novo assembler), that utilizes a novel k-mer clustering approach from the overlap-layout-consensus concept to deal with the sequencing errors generated by the Illumina platform. We further evaluate Clover's performance against several de Bruijn graph assemblers (ABySS, SOAPdenovo, SPAdes and Velvet), overlap-layout-consensus assemblers (Bambus2, CABOG and MSR-CA) and string graph assembler (SGA) on three datasets (Staphylococcus aureus, Rhodobacter sphaeroides and human chromosome 14). The results show that Clover achieves a superior assembly quality in terms of corrected N50 and E-size while remaining a significantly competitive in run time except SOAPdenovo. In addition, Clover was involved in the sequencing projects of bacterial genomes Acinetobacter baumannii TYTH-1 and Morganella morganii KT. CONCLUSIONS: The marvel clustering-based approach of Clover that integrates the flexibility of the overlap-layout-consensus approach and the efficiency of the de Bruijn graph method has high potential on de novo assembly. Now, Clover is freely available as open source software from https://oz.nthu.edu.tw/~d9562563/src.html .

Recently, Deep Learning has been applied to many medical domains, such as medical image analysis, bioinformatic, biochemistry, drug design, and so forth, to improve the performance that is superior to traditional computational approaches; especially in computer-aided drug design. Many AI-driven drug discovery startups have utilized deep learning methodology to achieve the significant improvement of searching candidate compounds, predicting functions, and so forth. Therefore, using AI to facilitate drug design is the trend in the coming future. In this study, a comprehensive review of the current state-of-the-art in Computer-Aided Drug Design using deep learning methods is presented. Meanwhile, the challenges and potential of these methods are also highlighted.

MOTIVATION: High-throughput sequencing technology has revolutionized the study of metagenomics and cancer evolution. In a relatively simple environment, a metagenomics sequencing data is dominated by a few species. By analyzing the alignment of reads from microbial species, single nucleotide polymorphisms can be discovered and the evolutionary history of the populations can be reconstructed. The ever-increasing read length will allow more detailed analysis about the evolutionary history of microbial or tumor cell population. A simulator of shotgun sequences from such populations will be helpful in the development or evaluation of analysis algorithms. RESULTS: Here, we described an efficient algorithm, MetaSMC, which simulates reads from evolving microbial populations. Based on the coalescent theory, our simulator supports all evolutionary scenarios supported by other coalescent simulators. In addition, the simulator supports various substitution models, including Jukes-Cantor, HKY85 and generalized time-reversible models. The simulator also supports mutator phenotypes by allowing different mutation rates and substitution models in different subpopulations. Our algorithm ignores unnecessary chromosomal segments and thus is more efficient than standard coalescent when recombination is frequent. We showed that the process behind our algorithm is equivalent to Sequentially Markov Coalescent with an incomplete sample. The accuracy of our algorithm was evaluated by summary statistics and likelihood curves derived from Monte Carlo integration over large number of random genealogies. AVAILABILITY AND IMPLEMENTATION: MetaSMC is written in C. The source code is available at https://github.com/tarjxvf/metasmc. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Recently, deep learning technologies have been utilized in many scientific domains successfully. Convolution neural networks are common used in image understanding problems. However, to train a convolution neural network model with huge amount of images is time-consuming task. Most of deep learning frameworks, such as Caffe, TensorFlow, Torch, Keras, MxNet, and so forth, support GPU to train model fast; especially executing these models on multiple GPUs. In this work, we present the comparison of computation performance of AlexNet among different GPU servers and hyperparameters. The results shows that GPU servers with high bandwidth rate, NVLINK, can achieve better performance than others.

Due to the rapid increase in biological data dimension and acquisition rate, the traditional analysis methods are unable to achieve acceptable accuracy. Recently, Deep learning technologies have shown outstanding results in many domains; especially in pattern recognition in the field of bioinformatics. In this paper, we provide background of what deep learning and its frameworks. In addition, we review the state-of-the-art algorithms based on GPU to presenting the usage of them to guide computational biologists to know how to leverage deep learning to improve their methods.

With the rapid growth of biological technology, large amount of biological data can be produced in few days or months. Many of common-used tools become computation-consuming in analyzing such big biological data. Cloud computing has emerged to provide the huge amount of computing power and play important role in development of bioinformatics tools. We propose a cloud computing framework that is able to easily deploy the bioinformatics tools on cloud virtualization platform based on Hadoop. This framework can work on the public cloud platform vendor such as Amazon EC2 and also private cloud platform. All the tools performed by cloud computing framework as Bioinformatics as a Services are available at http://bioinfo.cs.pu.edu.tw/CBBTS. The tools deployed on cloud platform by the proposed framework are tested in Providence University cloud platform and provided good proportional acceleration when scaled out onto many computational units. In the big biological data era, cloud computing based solutions are important role to develop bioinformatics services over internet. In the work, the proposed framework is able to simply deploy several well-known bioinformatics tools on cloud virtualization platform and as web services. This framework can work on the public cloud platform vendor such as Amazon EC2 and also private cloud platform.

The papers in this special section were presented at the 2014 International Conference on Genome Informatics (GIW).

In the 21stcentury, antibiotic resistance has become a crucial and growing phenomenon in contemporary medicine. Multidrug resistant leads that antibiotics cannot be used to treat infections. In this paper, we propose a novel and efficient method to identify drug resistance genes from raw reads produced by next generation sequencing technology for metagenomes. The experimental results show that the proposed method is able to identify the resistance genes of Acinetobacter baumannii, TYTH-1.

BACKGROUND: In the last decade, a considerable amount of research has been devoted to investigating the phylogenetic properties of organisms from a systems-level perspective. Most studies have focused on the classification of organisms based on structural comparison and local alignment of metabolic pathways. In contrast, global alignment of multiple metabolic networks complements sequence-based phylogenetic analyses and provides more comprehensive information. RESULTS: We explored the phylogenetic relationships between microorganisms through global alignment of multiple metabolic networks. The proposed approach integrates sequence homology data with topological information of metabolic networks. In general, compared to recent studies, the resulting trees reflect the living style of organisms as well as classical taxa. Moreover, for phylogenetically closely related organisms, the classification results are consistent with specific metabolic characteristics, such as the light-harvesting systems, fermentation types, and sources of electrons in photosynthesis. CONCLUSIONS: We demonstrate the usefulness of global alignment of multiple metabolic networks to infer phylogenetic relationships between species. In addition, our exhaustive analysis of microbial metabolic pathways reveals differences in metabolic features between phylogenetically closely related organisms. With the ongoing increase in the number of genomic sequences and metabolic annotations, the proposed approach will help identify phenotypic variations that may not be apparent based solely on sequence-based classification.

High-throughput technology for genotyping has made genome-wide associations possible. Single nucleotide polymorphism (SNP) data derived from array-based technology are usually flawed due to missing data, although they have generally high call rates and good concordance rates across different genotype calling schemes. Missing SNPs can bias the results of association analyses and hence loci with missing data are removed in some studies. Imputation is a method of compensating for the missing data by filling in the most probable values. It can increase the power of the association study and does not involve extra cost to genotype the missing SNPs. In this article, we propose a simple imputation method (Simpute) that takes advantage of the high resolution of SNPs in either the array platform or the mass parallel sequencing platform. It is based on the linkage disequilibrium (LD) structure of the chromosome and only two nearby SNPs are needed to fill in the missing data. Simpute does not use any reference data. We tested this method by randomly masking the genotype data of the international Hap Map phase III project, and the evaluation is made on Chromosome 21. The proposed Simpute algorithm was compared with two algorithms. At highly linked SNP loci, it performs approximately well as BEAGLE, which is a general-purpose algorithm and integrates lots of information. Simpute outperforms the second algorithm proposed by Jung et al., which does not use any reference samples as Simpute. The best feature of Simpute is its computational efficiency with complexity of order, where n is the number of missing SNPs, w is the number of the positions of the missing SNPs and m is the number of people considered. Simpute provides a simple, accurate and fast solution to the whole genome imputation. We have demonstrated that when the SNPs are densely distributed on the chromosome with high linkage disequilibrium between adjacent loci, there is no need to adopt complicated algorithms. Simpute is suitable for regular screening of the large scale SNP genotyping especially when the sample size is large and the efficiency is a major issue of the workflow.

Recently, many new next-generation sequencing techniques have been proposed. These techniques can produce lot of short reads rapidly. Hence, a number of tools have been developed to map these short reads to the genome. However, with more and more reads sequenced and the length of reads increases, these tools require high memory usage and huge computational cost and are also impractical for utilization. As the GPU has become increasingly more powerful and ubiquitous, many scientific applications have been implemented to enhance the computational performance on GPU platform. In this paper, we proposed a method, CUDA-FRESCO, to map the short reads to the genome by using CUDA on GPU platform. The experimental results present that CUDA-FRESCO can achieve dramatic speed up than other tools. CUDA-FRESCO can be alternative tool for biologists to map the short reads fast.

BACKGROUND: Identifying key components in biological processes and their associations is critical for deciphering cellular functions. Recently, numerous gene expression and molecular interaction experiments have been reported in Saccharomyces cerevisiae, and these have enabled systematic studies. Although a number of approaches have been used to predict gene functions and interactions, tools that analyze the essential coordination of functional components in cellular processes still need to be developed. RESULTS: In this work, we present a new approach to study the cooperation of functional modules (sets of functionally related genes) in a specific cellular process. A cooperative module pair is defined as two modules that significantly cooperate with certain functional genes in a cellular process. This method identifies cooperative module pairs that significantly influence a cellular process and the correlated genes and interactions that are essential to that process. Using the yeast cell cycle as an example, we identified 101 cooperative module associations among 82 modules, and importantly, we established a cell cycle-specific cooperative module network. Most of the identified module pairs cover cooperative pathways and components essential to the cell cycle. We found that 14, 36, 18, 15, and 20 cooperative module pairs significantly cooperate with genes regulated in early G1, late G1, S, G2, and M phase, respectively. Fifty-nine module pairs that correlate with Cdc28 and other essential regulators were also identified. These results are consistent with previous studies and demonstrate that our methodology is effective for studying cooperative mechanisms in the cell cycle. CONCLUSIONS: In this work, we propose a new approach to identifying condition-related cooperative interactions, and importantly, we establish a cell cycle-specific cooperation module network. These results provide a global view of the cell cycle and the method can be used to discover the dynamic coordination properties of functional components in other cellular processes.

BACKGROUND: Signal transduction is the major mechanism through which cells transmit external stimuli to evoke intracellular biochemical responses. Understanding relationship between external stimuli and corresponding cellular responses, as well as the subsequent effects on downstream genes, is a major challenge in systems biology. Thus, a systematic approach to integrate experimental data and qualitative knowledge to identify the physiological consequences of environmental stimuli is needed. RESULTS: In present study, we employed a genetic algorithm-based Boolean model to represent NF-κB signaling pathway. We were able to capture feedback and crosstalk characteristics to enhance our understanding on the acute and chronic inflammatory response. Key network components affecting the response dynamics were identified. CONCLUSIONS: We designed an effective algorithm to elucidate the process of immune response using comprehensive knowledge about network structure and limited experimental data on dynamic responses. This approach can potentially be implemented for large-scale analysis on cellular processes and organism behaviors.

MOTIVATION: Carbohydrate-binding modules (CBMs) share similar secondary and tertiary topology, but their primary sequence identity is low. Computational identification of ligand-binding residues allows biologists to better understand the protein-carbohydrate binding mechanism. In general, functional characterization can be alternatively solved by alignment-based manners. As alignment accuracy based on conventional methods is often sensitive to sequence identity, low sequence identity among query sequences makes it difficult to precisely locate small portions of relevant features. Therefore, we propose a feature-incorporated alignment (FIA) to flexibly align conserved signatures in CBMs. Then, an FIA-based target-template prediction model was further implemented to identify functional ligand-binding residues. RESULTS: Arabidopsis thaliana CBM45 and CBM53 were used to validate the FIA-based prediction model. The predicted ligand-binding residues residing on the surface in the hypothetical structures were verified to be ligand-binding residues. In the absence of 3D structural information, FIA demonstrated significant improvement in the estimation of sequence similarity and identity for a total of 808 sequences from 11 different CBM families as compared with six leading tools by Friedman rank test.

BACKGROUND: DNA signatures are distinct short nucleotide sequences that provide valuable information that is used for various purposes, such as the design of Polymerase Chain Reaction primers and microarray experiments. Biologists usually use a discovery algorithm to find unique signatures from DNA databases, and then apply the signatures to microarray experiments. Such discovery algorithms require to set some input factors, such as signature length l and mismatch tolerance d, which affect the discovery results. However, suggestions about how to select proper factor values are rare, especially when an unfamiliar DNA database is used. In most cases, biologists typically select factor values based on experience, or even by guessing. If the discovered result is unsatisfactory, biologists change the input factors of the algorithm to obtain a new result. This process is repeated until a proper result is obtained. Implicit signatures under the discovery condition (l, d) are defined as the signatures of length < or = l with mismatch tolerance > or = d. A discovery algorithm that could discover all implicit signatures, such that those that meet the requirements concerning the results, would be more helpful than one that depends on trial and error. However, existing discovery algorithms do not address the need to discover all implicit signatures. RESULTS: This work proposes two discovery algorithms - the consecutive multiple discovery (CMD) algorithm and the parallel and incremental signature discovery (PISD) algorithm. The PISD algorithm is designed for efficiently discovering signatures under a certain discovery condition. The algorithm finds new results by using previously discovered results as candidates, rather than by using the whole database. The PISD algorithm further increases discovery efficiency by applying parallel computing. The CMD algorithm is designed to discover implicit signatures efficiently. It uses the PISD algorithm as a kernel routine to discover implicit signatures efficiently under every feasible discovery condition. CONCLUSIONS: The proposed algorithms discover implicit signatures efficiently. The presented CMD algorithm has up to 97% less execution time than typical sequential discovery algorithms in the discovery of implicit signatures in experiments, when eight processing cores are used.

BACKGROUND: Signal transduction is the major mechanism through which cells transmit external stimuli to evoke intracellular biochemical responses. Diverse cellular stimuli create a wide variety of transcription factor activities through signal transduction pathways, resulting in different gene expression patterns. Understanding the relationship between external stimuli and the corresponding cellular responses, as well as the subsequent effects on downstream genes, is a major challenge in systems biology. Thus, a systematic approach is needed to integrate experimental data and theoretical hypotheses to identify the physiological consequences of environmental stimuli. RESULTS: We proposed a systematic approach that combines forward and reverse engineering to link the signal transduction cascade with the gene responses. To demonstrate the feasibility of our strategy, we focused on linking the NF-kappaB signaling pathway with the inflammatory gene regulatory responses because NF-kappaB has long been recognized to play a crucial role in inflammation. We first utilized forward engineering (Hybrid Functional Petri Nets) to construct the NF-kappaB signaling pathway and reverse engineering (Network Components Analysis) to build a gene regulatory network (GRN). Then, we demonstrated that the corresponding IKK profiles can be identified in the GRN and are consistent with the experimental validation of the IKK kinase assay. We found that the time-lapse gene expression of several cytokines and chemokines (TNF-alpha, IL-1, IL-6, CXCL1, CXCL2 and CCL3) is concordant with the NF-kappaB activity profile, and these genes have stronger influence strength within the GRN. Such regulatory effects have highlighted the crucial roles of NF-kappaB signaling in the acute inflammatory response and enhance our understanding of the systemic inflammatory response syndrome. CONCLUSION: We successfully identified and distinguished the corresponding signaling profiles among three microarray datasets with different stimuli strengths. In our model, the crucial genes of the NF-kappaB regulatory network were also identified to reflect the biological consequences of inflammation. With the experimental validation, our strategy is thus an effective solution to decipher cross-talk effects when attempting to integrate new kinetic parameters from other signal transduction pathways. The strategy also provides new insight for systems biology modeling to link any signal transduction pathways with the responses of downstream genes of interest.

Multiple sequence alignment is widely applied to discover core conserved regions among query sequences. However, the major deficiency is that alignment accuracy is extremely sensitive to primary sequence identity, which causes alignment of low identity sequences difficult. We propose a feature-integrated model called feature-incorporated alignment (FIA) which integrates relevant biological characteristics including aromatic amino acids, hydrophilicity, beta-stranded structure, and BLOSUM62 matrix to locate ligand-binding residue in carbohydrate binding modules (CBMs), a protein family with fairly low sequence identify but highly functional correlation. The results indicated that FIA can not only detect aromatic residues on the outer surface of structure, but also achieve better accuracy than ClustalW2 and DIALIGN-TX on entropy criterion in all three test datasets from CBMs. Computational analysis in CBMs can facilitate the discovery of crucial ligand-binding residues of carbohydrate-active enzymes.

Sequence alignment is a fundamental problem in the computational biology. Many alignment methods have been proposed in the literature, such as pair-wise sequence alignment (2SA), syntenic alignment, multiple sequence alignment (MSA) and constraint multiple sequence alignment, etc. Three-sequence alignment (3SA) problem has been proposed and discussed in the computational biology and proved that the alignment results from 3SA are better than those from 2SA under some conditions. However, 3SA problem is less discussed over the past decade due to the computer capability. 3SA problem now is worthy to discuss due to the powerful computer and more and more genome and protein sequences. In this paper, an efficient parallel algorithm (P3SA) is proposed to solve 3SA problem. The P3SA method requires 0(n2/p) space complexity and 0(n3/p) time complexity. The experimental results show that P3SA algorithm is applicable and achieves a satisfied speed-up.

BACKGROUND: Members of a protein family often have highly conserved sequences; most of these sequences carry identical biological functions and possess similar three-dimensional (3-D) structures. However, enzymes with high sequence identity may acquire differential functions other than the common catalytic ability. It is probable that each of their variable regions consists of a unique peptide motif (UPM), which selectively interacts with other cellular proteins, rendering additional biological activities. The ability to identify and localize such UPMs is paramount in recognizing the characteristic role of each member of a protein family. RESULTS: We have developed a reinforced merging algorithm (RMA) with which non-gapped UPMs were identified in a variety of query protein sequences including members of human ribonuclease A (RNaseA), epidermal growth factor receptor (EGFR), matrix metalloproteinase (MMP), and Sma-and-Mad related protein families (Smad). The UPMs generally occupy specific positions in the resolved 3-D structures, especially the loop regions on the structural surfaces. These motifs coincide with the recognition sites for antibodies, as the epitopes of four monoclonal antibodies and two polyclonal antibodies were shown to overlap with the UPMs. Most of the UPMs were found to correlate well with the potential antigenic regions predicted by PROTEAN. Furthermore, an accuracy of 70% can be achieved in terms of mapping a UPM to an epitope. CONCLUSION: Our study provides a bioinformatic approach for searching and predicting potential epitopes and interacting motifs that distinguish different members of a protein family.

In this article, we investigate two spanning tree problems of graphs with k given sources. Let G = (V,E,w) be an undirected graph with nonnegative edge lengths and S ⊂ V a set of k specified sources. The first problem is the k-source maximum vertex shortest paths spanning tree (k-MVST) problem, in which we want to find a spanning tree T such that the maximum total distance from any vertex to all sources is minimized, that is, we want to minimize maxv∈V{∑s∈SdT(s,v)}, in which dT(s,v) is the length of the path between s and v on T. The other problem is the k-source maximum source shortest paths spanning tree (k-MSST)problem, in which the objective function is the maximum total distance from any source to all vertices, that is, max s∈S{∑v∈VdT(s,v)}. In this article, we present a polynomial time approximation scheme (PTAS) for the 2-MVST problem. For the 2-MSST problem, we first give (2 +ε)-approximation algorithm for any ε> 0, and then present a PTAS for the case that the input graphs are restricted to metric graphs. Finally, we show that there are simple 3-approximation algorithms for both problems with arbitrary k. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 147–156 2006

The classification of protein structures is essential for their function determination in bioinformatics. The success of the protein structure classification depends on two factors: the computational methods used and the features selected. In this paper, we use a combinatorial fusion analysis technique to facilitate feature selection and combination for improving predictive accuracy in protein structure classification. When applying these criteria to our previous work, the resulting classification has an overall prediction accuracy rate of 87% for four classes and 69.6% for 27 folding categories. These rates are significantly higher than our previous work and demonstrate that combinatorial fusion is a valuable method for protein structure classification.

SUMMARY: ROBIN is a web server for analyzing genome rearrangement of block-interchanges between two chromosomal genomes. It takes two or more linear/circular chromosomes as its input, and computes the number of minimum block-interchange rearrangements between any two input chromosomes for transforming one chromosome into another and also determines an optimal scenario taking this number of rearrangements. The input can be either bacterial-size sequence data or landmark-order data. If the input is sequence data, ROBIN will automatically search for the identical landmarks that are the homologous/conserved regions shared by all the input sequences.

In this paper, we solve the maximum agreement subtree problem for a set T of k rooted, leaf-labelled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn/sup 3/)-time dynamic programming algorithm proposed by Farach et al. and Bryant can be implemented in O(n/sup 2/log/sup k-1/n) and O(k/spl middot/n/sup 3-(1/k-1)/) using the k-dimensional binary search tree and the k-dimensional range search tree, respectively.

The homology search within genomic databases is a fundamental and crucial work for biological knowledge discovery. With exponentially increasing sizes and accesses of databases, the filtration approach, which filters impossible homology candidates to reduce the time for homology verification, becomes more important in bioinformatics. Most of known gram-based filtration approaches, like QUASAR, in the literature have limited error tolerance and would conduct potentially higher false-positives. In this paper, we present an IDC-based lossless filtration algorithm with guaranteed seriate coverage and error tolerance for efficient homology discovery. In our method, the original work of homology extraction with requested seriate coverage and error levels is transformed to a longest increasing subsequence problem with range constraints, and an efficient algorithm is proposed for the problem in this paper. The experimental results show that the method significantly outperforms QUASAR. On some comparable sensitivity levels, our homology filter would make the discovery more than three orders of magnitude faster than that QUASAR does, and more than four orders faster than the exhaustive search.

Abstract Let G = ({1,…, n}, E, w) be an undirected graph with nonnegative edge weights w and let aij be the nonnegative requirement between vertices i and j. For any spanning subgraph H of G, the weight of H is the total weight of its edges and the routing cost of H is Σi

This paper presents an optimal sampling external selection (SES) algorithm to select k-th smallest item in large data sets for the two-level memory model. Based on the SES algorithm, two algorithms SES/DASK (dynamic assigned sorting key) and SES/FASK (fixed assigned sorting key) are also proposed which are applied to the worldwide selection problem in the Internet environment. We use the sampling information scheme to form an elegant and simple algorithm to reduce the number of disk I/Os. Especially, our algorithm is more efficient for the multiple selections.

The idea is to interconnect test items to reuse memory states left from the previous test item for saving initialization and verification sequences. Meanwhile, signal settling time of the tester between two consecutive test items being applied can also be minimized since all test items are connected together into a continuous one. The interconnection problem is transformed to the Rural Chinese Postman (RCP) problem. The RCP problem is a famous NP-hard problem, one way to solve the RCP problem is by modeling as an integer linear programming (ILP) model. However, in the worst case, it will incur an exponential number of constraints; therefore, it is not suitable for practical usage. Instead of putting all constraints at once, we generate and solve a number of successive ILP models with the smaller number of constraints. The total numbers of iterations and constraints applied to solve ILP models are analyzed and compared.

Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the tree. Finding a spanning tree of minimum routing cost is NP-hard, even when the costs obey the triangle inequality. We show that the general case is in fact reducible to the metric case and present a polynomial-time approximation scheme valid for both versions of the problem. In particular, we show how to build a spanning tree of an n-vertex weighted graph with routing cost at most $(1+\epsilon)$ of the minimum in time $O(n^{O({\frac{1}{\epsilon}}% )})$. Besides the obvious connection to network design, trees with small routing cost also find application in the construction of good multiple sequence alignments in computational biology. The communication cost spanning tree problem is a generalization of the minimum routing cost tree problem where the routing costs of different pairs are weighted by different requirement amounts. We observe that a randomized O(log n log log n)-approximation for this problem follows directly from a recent result of Bartal, where n is the number of nodes in a metric graph. This also yields the same approximation for the generalized sum-of-pairs alignment problem in computational biology.

Efficient emulations provide general methods to convert algorithms designed on a network into algorithms on smaller networks (with the same interconnection structure). In this paper, an optimal emulation for trees is proposed. With slight modification, our emulation can be applied to X-trees without loss of any efficiency. By the strategy of our emulation, optimal emulations for m-ary trees and pyramids can be obtained. An extended problem of the emulation problem on trees is to emulate a weighted tree, in which every node is associated with a weight by a smaller tree. In this paper, we also consider the extended problem and show that the problem is NP-hard.

In this paper, fast algorithms for simulating the CRCW shared-memory computer on reconfigurable meshes are proposed.

A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system, taking both external synchronization and input/output operation costs into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification and a heuristic algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, the heuristic algorithm yields a minimum-cost test sequence. The X.25 DTE and ISO Class 0 Transport protocols are proved to possess this specific property. otherwise, the heuristic algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 Network-side protocol is shown to be the cost sum of an input/output operation and an external synchronization operation.>