The human leukocyte antigen (HLA) system or complex plays an essential role in regulating the immune system in humans. Accurate prediction of peptide binding with HLA can efficiently help to identify those neoantigens which potentially make a big difference in immune drug development. HLA is one of the most polymorphic genetic systems in humans and thousands of HLA allelic versions exist [1]. Due to the high polymorphism of the HLA complex, it remains difficulties to accurately predict the binding affinity. In this paper, we present a new algorithm to combine a convolutional neural network and long short-term memory to solve this problem. Compared with other current popular models, our model achieved state-of the-art results.

The majority of current dimension reduction methods are restricted to the use of spectral information, when the spatial information is left out. In order to overcome this defect, two different solutions: patch-based and tensor-patch-based approaches, were studied in this paper. This paper applies the two solutions to a group of graph-based dimension reduction methods. We found that the patch-based and tensor-patch-based variations greatly boost the final classification results by 5%-15% from the traditional methods. As graph-based methods heavily rely on the calculation of adjacency graphs/weight matrices, this paper proposed the use of a new method: weighted region covariance matrix, to produce the adjacency graphs/weight matrices. In results, the newly proposed method can further improve the dimension reduction results in both the patch-based and tensor-patch-based methods. To reduce the intense computation in the adjacency graphs/weight matrix calculation, the principle component analysis (PCA) is proposed by this paper as a preprocess step.

Glycosylation is a frequently observed post-translational modification on proteins. Currently, tandem mass spectrometry (MS/MS) serves as an efficient analytical technique for characterizing structures of oligosaccharides. However, developing effective computational approaches for identifying glycan structures from mass spectra is still a great challenge in glycoproteomics research. In this study, we proposed an approach for matching the input spectra with glycan structures acquired from a glycan structure database by incorporating a de novo sequencing assisted ranking scheme. The proposed approach is implemented as a software tool, GlycoNovoDB, for automated glycan structure identification from HCD MS/MS of glycopeptides. Experimental results showed that GlycoNovoDB can identify glycans effectively and has better performance than our previously proposed de novo sequencing algorithm as well as another software GlycoMaster DB.

MOTIVATION: Enzymatic digestion under appropriate reducing conditions followed by mass spectrometry analysis has emerged as the primary method for disulfide bond analysis. The large amount of mass spectral data collected in the mass spectrometry experiment requires effective computational approaches to automate the interpretation process. Although different approaches have been developed for such purpose, they always choose to ignore the frequently observed internal ion fragments and they lack a reasonable quality control strategy and calibrated scoring scheme for the statistical validation and ranking of the reported results. RESULTS: In this research, we present a new computational approach, DISC (DISulfide bond Characterization), for matching an input MS/MS spectrum against the putative disulfide linkage structures hypothetically constructed from the protein database. More specifically, we consider different ion types including a variety of internal ions that frequently observed in mass spectra resulted from disulfide linked peptides, and introduce an effective two-layer scoring scheme to evaluate the significance of the matching between spectrum and structure, based on which we have also developed a useful target-decoy strategy for providing quality control and reporting false discovery rate in the final results. Systematic experiments conducted on both low-complexity and high-complexity datasets demonstrated the efficiency of our proposed method for the identification of disulfide bonds from MS/MS spectra, and showed its potential in characterizing disulfide bonds at the proteome scale instead of just a single protein. AVAILABILITY AND IMPLEMENTATION: Software is available for downloading at http://www.csd.uwo.ca/yliu766/. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Mixture spectra occur quite frequently in a typical wet-lab mass spectrometry experiment, which result from the concurrent fragmentation of multiple precursors. The ability to efficiently and confidently identify mixture spectra is essential to alleviate the existent bottleneck of low mass spectra identification rate. However, most of the traditional computational methods are not suitable for interpreting mixture spectra, because they still take the assumption that the acquired spectra come from the fragmentation of a single precursor. In this manuscript, we formulate the mixture spectra de novo sequencing problem mathematically, and propose a dynamic programming algorithm for the problem. Additionally, we use both simulated and real mixture spectra data sets to verify the merits of the proposed algorithm.

BACKGROUND: De novo peptide sequencing via tandem mass spectrometry (MS/MS) has been developed rapidly in recent years. With the use of spectra pairs from the same peptide under different fragmentation modes, performance of de novo sequencing is greatly improved. Currently, with large amount of spectra sequenced everyday, spectra libraries containing tens of thousands of annotated experimental MS/MS spectra become available. These libraries provide information of the spectra properties, thus have the potential to be used with de novo sequencing to improve its performance. RESULTS: In this study, an improved de novo sequencing method assisted with spectra library is proposed. It uses spectra libraries as training datasets and introduces significant scores of the features used in our previous de novo sequencing method for HCD and ETD spectra pairs. Two pairs of HCD and ETD spectral datasets were used to test the performance of the proposed method and our previous method. The results show that this proposed method achieves better sequencing accuracy with higher ranked correct sequences and less computational time. CONCLUSIONS: This paper proposed an advanced de novo sequencing method for HCD and ETD spectra pair and used information from spectra libraries and significant improved previous similar methods.

Large-scale comparison or similarity search of genomic DNA and protein sequence is of fundamental importance in modern molecular biology. To perform DNA and protein sequence similarity search efficiently, seeding (or filtration) method has been widely used where only sequences sharing a common pattern or "seed" are subject to detailed comparison. Therefore these methods trade search sensitivity with search speed. In this paper, we introduce a new seeding method, called spaced k-mer neighbors, which provides a better tradeoff between the sensitivity and speed in protein sequence similarity search. With the method of spaced k-mer neighbors, for each spaced k-mer, a set of spaced k-mers is selected as its neighbors. These pre-selected spaced k-mer neighbors are then used to detect hits between query sequence and database sequences. We propose an efficient heuristic algorithm for the spaced neighbor selection. Our computational experimental results demonstrate that the method of spaced k-mer neighbors can improve the overall tradeoff efficiency over existing seeding methods.

In DNA and protein sequence similarity search, seeding (or filtration) has been widely used to trade search sensitivity with search speed. In this paper, a new seeding method, called spaced k-mer neighbors, is introduced to provide a more efficient tradeoff between the speed and sensitivity in protein similarity search. The new method pre-selects a set of spaced k-mers as neighbors, and uses the neighbors to detect hits between the query and database sequences. An efficient heuristic algorithm is proposed for the neighbor selection. We demonstrate that the method can improve the tradeoff efficiency over existing seeding methods.

Similarity metric is important in many applications. In some applications, it is desirable to normalize the similarity metric so as to yield a more meaningful insight of the situation, for example, in comparison of long genomic sequences and comparative gene prediction. In extending the content of a previous work involving formal definition of the concept known as similarity, we give new formulas for normalizing similarity metrics which satisfy the formal definition of the normalized similarity metric. We also describe how these formulas may be utilized in an appropriate application domain in which the use of normalized similarity metric is desirable.

In this paper, we study the issue of sensor network deployment using limited mobility sensors. By limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring a minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the optimal maximum flow-based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the simple peak-pit-based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements, and messaging overhead under different initial deployment scenarios.

In this paper we present RADAR, a web-based toolkit for RNA data analysis and research. The toolkit is capable of performing database search, multiple structure alignment, and pairwise structure comparison. In addition, RADAR provides two salient features: (1) constrained alignment of RNA secondary structures, and (2) prediction of the consensus for a set of RNA secondary structures. RADAR assists scientists in performing many important RNA mining operations, including understanding the functionality of RNA sequences, the detection of structural RNA motifs and the clustering of RNA molecules, among others. The toolkit is fully operational and accessible on the Web at http://datalab.njit.edu/biodata/rna/RSmatch/server.htm.

Genome rearrangement is a new and important research area that studies the gene orders and the evolution of gene families. With the development of fast sequencing techniques, large-scale DNA molecules are investigated with respect to the relative order of genes in them. Contrary to the traditional alignment approach, genome rearrangements are based on comparison of gene orders. Recently, it became a topic capturing wide attention. In this paper, we cover many kinds of rearrangement events such as reversal, transposition, translocation, fussion, fission, and so on. Different types of distances between genomes or chromosomes are discussed. A variety of mathematic models are included.

In this paper, we present an embedding technique, called MetricMap, which is capable of estimating distances in a pseudometric space. Given a database of objects and a distance function for the objects, which is a pseudometric, we map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such an embedding technique can be used as an approximate oracle to process a broad class of distance-based queries. It is also adaptable to data mining applications such as data clustering and classification. We present the theory underlying MetricMap and conduct experiments to compare MetricMap with other methods including MVP-tree and M-tree in processing the distance-based queries. Experimental results on both protein and RNA data show the good performance and the superiority of MetricMap over the other methods.

Recent advances in RNA studies show that the well-ordered, structured RNAs perform a broad functions in various biological mechanisms. Included among these functions are regulations of gene expression at multiple levels by diversified ribozymes and various RNA regulatory elements. The discovered microRNAs (miRNAs) with a distinct stem-loops are a new class of RNA regulatory elements. The prediction of those well-ordered folding sequences (WFS) associated with the RNA regulatory elements in genomic sequences is very helpful for our understandings of RNA-based gene regulations. We present here a new computational method in searching for the conserved WFS in genomes. In the method, the WFS is assessed by a quantitative measure E diff that is defined as the difference of free energies between the computed optimal structure (OS) and its corresponding optimal restrained structure where all the previous base pairings in the OS are forbidden. From those WFS with high E diff scores, the conserved WFS is determined by computing the maximal similarity score (MSS) between the two compared structures. In practice, we first search for those distinct WFS with high statistical significance in genomic sequences and then seek for those conserved WFS with high MSS. The potential and implications of our discoveries in the genome of Caenorhabditis elegans are discussed.

A wavelet transform based method for road extraction is introduced. It characterizes the edges of roads in high-resolution remotely sensed images through their multi-scale wavelet transforms. Road networks are extracted efficiently from the images.

An unordered labeled tree is a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant. This paper presents an approach to the nearest neighbor search problem for these trees. Given a database D of unordered labeled trees and a query tree Q, the goal is to find those trees in D that "approximately" contain Q. Our approach is based on storing the paths of the trees in a suffix array and then counting the number of mismatching paths between the query tree and a data tree. To speed up a search, we use a hash-based technique to filter out unqualified data trees at an early stage of the search. Experimental results obtained by running our techniques on phylogenetic trees and synthetic data demonstrate the good performance of the proposed approach. We also discuss the use of our work in XML and scientific database management.

Presents a method for finding patterns in 3D graphs. Each node in a graph is an undecomposable or atomic unit and has a label. Edges are links between the atomic units. Patterns are rigid substructures that may occur in a graph after allowing for an arbitrary number of whole-structure rotations and translations as well as a small number (specified by the user) of edit operations in the patterns or in the graph. (When a pattern appears in a graph only after the graph has been modified, we call that appearance "approximate occurrence.") The edit operations include relabeling a node, deleting a node and inserting a node. The proposed method is based on the geometric hashing technique, which hashes node-triplets of the graphs into a 3D table and compresses the label-triplets in the table. To demonstrate the utility of our algorithms, we discuss two applications of them in scientific data mining. First, we apply the method to locating frequently occurring motifs in two families of proteins pertaining to RNA-directed DNA polymerase and thymidylate synthase and use the motifs to classify the proteins. Then, we apply the method to clustering chemical compounds pertaining to aromatic compounds, bicyclicalkanes and photosynthesis. Experimental results indicate the good performance of our algorithms and high recall and precision rates for both classification and clustering.

Arc-annotated sequences are useful in representiug the structural information of RNA sequences. Typically, RNA secondary and tertiary structures could be represented by a set of nested arcs and a set of crossing arcs, respectively. As the specified RNA functions are determined by the specified molecular confirmation and therefore the specified secondary and tertiary structures, the comparison between RNA secondary and tertiary structures have received much attention recently. In this paper, we propose the notion of edit distance to measure the similarity between two RNA secondary and tertiary structures, by incorporating the various edit operations performing on both bases and arcs (base-pairs). Several algorithms are presented to compute the edit distance two RNA sequences with various arc structures and under various score schemes, either exactly or approximately. Preliminary experimental tests confirm that our definition of edit distance and the computation model are among the most reasonable ones ever studied in the literature.

A distance-mapping algorithm takes a set of objects and a distance metric and then maps those objects to a Euclidean or pseudo-Euclidean space in such a way that the distances among objects are approximately preserved. Distancemapping algorithms are a useful tool for clustering and visualization in data intensive applications, because they replace expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. In this paper we present five distance-mapping algorithms and conduct experiments to compare their performance in data clustering applications. These include two algorithms called FastMap and MetricMap, and three hybrid heuristics that combine the two algorithms in different ways. Experimental results on both synthetic and RNA data show the superiority of the hybrid algorithms. The results imply that FastMap and MetricMap capture complementary information about distance metrics and therefore ca...

Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology and natural language processing. We consider a substructure of an ordered labeled tree T to be a connected subgraph of T. Given two ordered labeled trees T/sub 1/ and T/sub 2/ and an integer d, the largest approximately common substructure problem is to find a substructure U/sub 1/ of T/sub 1/ and a substructure U/sub 2/ of T/sub 2/ such that U/sub 1/ is within edit distance d of U/sub 2/ and where there does not exist any other substructure V/sub 1/ of T/sub 1/ and V/sub 2/ of T/sub 2/ such that V/sub 1/ and V/sub 2/ satisfy the distance constraint and the sum of the sizes of V/sub 1/ and V/sub 2/ is greater than the sum of the sizes of U/sub 1/ and U/sub 2/. We present a dynamic programming algorithm to solve this problem, which runs as fast as the fastest known algorithm for computing the edit distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to discovering motifs in multiple RNA secondary structures (which are ordered labeled trees).

Structural matching and discovery in documents such as SGML and HTML is important for data warehousing [6], version management [7, 11], hypertext authoring, digital libraries [4] and Internet databases. As an example, a user of the World Wide Web may be interested in knowing changes in an HTML document [2, 5, 10]. Such changes can be detected by comparing the old and new version of the document (referred to as structural matching of documents). As another example, in hypertext authoring, a user may wish to find the common portions in the history list of a document or in a database of documents (referred to as structural discovery of documents). In SIGMOD 95 demo sessions, we exhibited a software package, called TreeDiff [13], for comparing two latex documents and showing their differences. Given two documents, the tool represents the documents as ordered labeled trees and finds an optimal sequence of edit operations to transform one document (tree) to the other. An edit operation could be an insert, delete, or change of a node in the trees. The tool is so named because documents are represented and compared using approximate tree matching techniques [9, 12, 14].

Over the past several years we have created or borrowed algorithms for combinatorial pattern matching and pattern discovery on sequences [2] and trees.In matching problems, given a pattern, a set of data objects and a distance metric, we find the distance between the pattern and one or more data objects. In discovery problems by contrast, given a set of objects, a metric, and a distance, we seek a pattern that matches many of those objects within the given distance. (So, discovery is a lot like data mining.) Our toolkit performs both matching and discovery with current targeted applications in molecular biology and document comparison.

Presents some new techniques of spectral and spatial decorrelation in lossless data compression of remotely sensed imagery. These techniques provide methods to efficiently compute the optimal band combination and band ordering based on the statistical properties of Landsat-TM data. Experiments on several Landsat-TM images show that using both the spectral and the spatial nature of the remotely sensed data results in significant improvement over spatial decorrelation alone. These techniques result in higher compression ratios and are computationally inexpensive.>

The authors present some preliminary results of their ongoing study on subjective VQ distortion measure in the time/spatial domain. They first propose a context based distortion measure between two vectors. The new measure is intuitively appealing, and they include some empirical evidence for its subjective significance. Although the measure is formulated as a matrix norm, it is computationally no more difficult than the mean-squares error. This measure quantifies the quantization distortion in the context (shape) of the signal waveform, but it is amplitude-invariant. So they combine the context distortion measure with a weighted mean distortion measure to obtain a unified subjective distortion measure D. They show that D is a distance measure and can be easily computed. Moreover, the process of computing the centroid of a set of training vectors and designing the VQ codebook under the new subjective distortion measure D is as simple as the conventional VQ. Specifically, the LBG algorithm can be applied to design the subjective VQ codebook after a simple linear transformation of the vector space in which signal samples are originally taken. They also analytically relate their subjective distortion measure to the ubiquitous mean-squares measure, and demonstrate that the latter is only a special case of the former. They also observe that the mean-removed VQ in a sense clusters training vectors under the proposed context distortion measure.>

Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching (AGM) problem: given a pattern graph P and a data graph D, what is the distance between P and D? and what is the minimum distance between P and D when subgraphs can be freely removed from D? We show that no efficient algorithm can solve either variant of the AGM, unless P=NP. We then give a polynomial-time approximation algorithm to solve this problem.

We consider the problem of comparison between labeled graphs. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion, and relabel operations on graph nodes and edges. Specifically, we consider two variants of the approximate graph matching problem: Given a pattern graph P and a data graph D, what is the distance between P and D? What is the minimum distance between P and D when subgraphs can be freely removed from D? We first observe that no efficient algorithm con solve either variant of the problem, unless P=NP. Then we present several heuristic algorithms based on probabilistic hill climbing techniques. Finally we evaluate the accuracy and time efficiency of the heuristics by applying them to a set of generated graphs and DNA molecules.>

Suppose you are given a set of natural entities (e.g., proteins, organisms, weather patterns, etc.) that possess some important common externally observable properties. You also have a structural description of the entities (e.g., sequence, topological, or geometrical data) and a distance metric. Combinatorial pattern discovery is the activity of finding patterns in the structural data that might explain these common properties based on the metric.

Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation, and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called approximate-tree-by-example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple but powerful query language; graphical devices are provided to facilitate inputing the queries. The paper describes the architecture of ATBE, illustrates its use and describes some aspects of ATBE implementation. We also discuss the underlying algorithms and provide some sample applications.>

We consider the problem of comparison between unordered trees, i.e., trees for which the order among siblings is unimportant. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g., genetics) where data can naturally be characterized by unordered trees. In companion work, we have shown this problem to be NP-complete. This paper presents an efficient enumerative algorithm and several heuristics leading to approximate solutions. The algorithms are based on probabilistic hill climbing and bipartite matching techniques. The paper evaluates the accuracy and time efficiency of the heuristics by applying them to a set of trees transformed from industrial parts based on a previously proposed morphological model.>

New monotonicity properties of optimal scalar quantizers are discussed. These monotonicities reveal a globally optimal scalar quantizer structure depending on the probability mass functions and on the number of quantizer levels. By incorporating the monotone quantizer structure into a dynamic programming process, the time complexities of previous algorithms for designing globally optimal scalar quantizers can be significantly reduced for very general classes of distortion measures.>

The problem of comparison between unordered trees, i.e. trees for which the order among siblings is unimportant, is considered. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion, and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g. genetics) where data can naturally be characterized by unordered trees. It is observed that the problem is NP-complete. An enumerative algorithm and several heuristics leading to approximate solutions are given. The algorithms are based on probabilistic hill climbing and bipartite matching techniques. The accuracy and time efficiency of the heuristics are evaluated by applying them to a set of trees transformed from industrial parts based on a previously proposed morphological model.>

A new vector quantizer permits logarithmic-time encoding and yet performs better than the locally optimal quantizers generated by the LBG algorithm. The success is credited to an elaborated tree-structured optimization process in the codebook design.>

A description is presented of a system, called approximate-tree-by-example (ATBE), which supports AI applications that involve comparing ordered labeled trees or retrieving/extracting information from repositories of such trees. The ATBE system interacts with users through a powerful query language; graphical devices are provided to facilitate inputting the queries. The system is designed to be extensible, customizable, and portable, which makes it a very useful tool for tree pattern matching in various environments. The use of the tool is illustrated. Several examples taken directly from the complete implementation are discussed.>

In a previous paper, an algorithm was presented for analyzing multiple RNA secondary structures utilizing a multiple string alignment algorithm. In this paper we present another approach to the problem of comparing many secondary structures by utilizing a very efficient tree-matching algorithm that will compare two trees in O([T1] X [T2] X L1 X L2) in the worst case and very close to O([T1] X [T2]) for average trees representing secondary structures. The result of the pairwise comparison algorithm is then used with a cluster algorithm to produce a multiple structure clustering which can be displayed in a taxonomy tree to show related structures.

1. Problem Ordered labeled trees are trees whose nodes are labeled and in which the ° left-to-right order among siblings is significant. We consider the distance between two trees to be the minimum number of edit operations (insert, delete, and modify) necessary to transform one tree to another. We present three algorithms to find the distance. The first algorithm is a simple dynamic program-ming algorithm based on a postorder traversal whose complexity improves upon the best previ-ously published algorithm due to Tai (T79 in JACM). The second and third algorithms are parallel algorithms based on the application of suf-fix trees to the comparison problem. The cost of executing these algorithms is a monotonic increas-ing function of the distance between the two trees. Results Let trees T I and T2 have numbers of levels L i and L 2 respectively. Let k be the actual distance between T 1 and T2. Let N be rain (IT11, IT2]). The asymptotic running times (assuming a concurrent-read concurrent-write parallel random access machine) are: A lgor i thm T ime Processors Tai IT l lX [T2[xL~XL] Alg l [Tx [ × Ir=l xLI×L2

Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions:1. What is the distance between two trees? 2. What is the minimum distance between $T_1 $ and $T_2 $ when zero or more subtrees can be removed from $T_2 $? 3. Let the pruning of a tree at node n mean removing all the descendants of node n. The analogous question for prunings as for subtrees is answered. A dynamic programming algorithm is presented to solve the three questions in sequential time $O(|T_1 | \times |T_2 | \times \min ({\textit{depth}}(T_1 ),{\textit{leaves}}(T_1 )) \times \min ({\textit{depth}}(T_2 ),{\textit{leaves}}(T_2 )))$ and space $O(|T_1 | \times |T_2 |)$ compared with $O(|T_1 | \times |T_2 | \times ({\textit{depth}}(T_1 ))^2 \times ({\textit{depth}}(T_2 ))^2 )$ for the best previous published algorithm due to Tai [J. Assoc. Comput. Mach., 26 (1979), pp, 422-433]. Further, the algorithm presented here can be parallelized to give time $O(|T_1 | \times |T_2 |)$.