This paper is concerned with a subclass of deterministic pushdown transducers, called deterministic restricted one-counter transducers (droct's), and studies the equivalence problem for real-time droct's which accept by final state. After providing some properties of these droct's, we present a polynomial-time algorithm for checking the equivalence for these droct's.

The tree edit distance is one of the most widely used measures for comparison of tree structured data and has been used for analysis of RNA secondary structures, glycan structures, and vascular trees. However, it is known that the tree edit distance problem is NP-hard for unordered trees while it is polynomial time solvable for ordered trees. We have recently proposed a clique-based method for computing the tree edit distance between unordered trees in which each instance of the tree edit distance problem is transformed into an instance of the maximum vertex weighted clique problem and then an existing clique algorithm is applied. In this paper, we propose an improved clique-based method. Different from our previous method, the improved method is basically a dynamic programming algorithm that repeatedly solves instances of the maximum vertex weighted clique problem as sub-problems. Other heuristic techniques, which do not violate the optimality of the solution, are also introduced. When applied to comparison of large glycan structures, our improved method showed significant speed-up in most cases.

BACKGROUND: Measuring similarities between tree structured data is important for analysis of RNA secondary structures, phylogenetic trees, glycan structures, and vascular trees. The edit distance is one of the most widely used measures for comparison of tree structured data. However, it is known that computation of the edit distance for rooted unordered trees is NP-hard. Furthermore, there is almost no available software tool that can compute the exact edit distance for unordered trees. RESULTS: In this paper, we present a practical method for computing the edit distance between rooted unordered trees. In this method, the edit distance problem for unordered trees is transformed into the maximum clique problem and then efficient solvers for the maximum clique problem are applied. We applied the proposed method to similar structure search for glycan structures. The result suggests that our proposed method can efficiently compute the edit distance for moderate size unordered trees. It also suggests that the proposed method has the accuracy comparative to those by the edit distance for ordered trees and by an existing method for glycan search. CONCLUSIONS: The proposed method is simple but useful for computation of the edit distance between unordered trees. The object code is available upon request.

BACKGROUND: Progress in the life sciences cannot be made without integrating biomedical knowledge on numerous genes in order to help formulate hypotheses on the genetic mechanisms behind various biological phenomena, including diseases. There is thus a strong need for a way to automatically and comprehensively search from biomedical databases for related genes, such as genes in the same families and genes encoding components of the same pathways. Here we address the extraction of related genes by searching for densely-connected subgraphs, which are modeled as cliques, in a biomedical relational graph. RESULTS: We constructed a graph whose nodes were gene or disease pages, and edges were the hyperlink connections between those pages in the Online Mendelian Inheritance in Man (OMIM) database. We obtained over 20,000 sets of related genes (called 'gene modules') by enumerating cliques computationally. The modules included genes in the same family, genes for proteins that form a complex, and genes for components of the same signaling pathway. The results of experiments using 'metabolic syndrome'-related gene modules show that the gene modules can be used to get a coherent holistic picture helpful for interpreting relations among genes. CONCLUSION: We presented a data mining approach extracting related genes by enumerating cliques. The extracted gene sets provide a holistic picture useful for comprehending complex disease mechanisms.

We consider the protein threading problem with profiles in which constraints on distances between residues are given. Though it is known that protein threading with profiles can be solved efficiently using dynamic programming, we prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (protein data bank). The results show that constraints are useful to improve the alignment accuracy. These also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.