An optimal algorithm for querying tree structures and its applications in bioinformatics

Abstract

Trees and graphs are widely used to model biological databases. Providing efficient algorithms to support tree-based or graph-based querying is therefore an important issue. In this paper, we propose an optimal algorithm which can answer the following question: "Where do the root-to-leaf paths of a rooted labeled tree Q occur in another rooted labeled tree T?" in time O(m + Occ), where m is the size of Q and Occ is the output size. We also show the problem of querying a general graph is NP-complete and not approximable within nk for any k < 1, where n is the number of nodes in the queried graph, unless P = NP.