An optimal algorithm for querying tree structures and its applications in bioinformatics
Resource
ACM SIGMOD Record 33 (2): 21-26
ACM SIGMOD Record,33,21-26.
Journal
SIGMOD Record
Journal Volume
33
Journal Issue
2
Pages
21-26
Date Issued
2004
Date
2004
Author(s)
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 approximate within nk for any k < 1, where n is the number of nodes in the queried graph, unless P = NP.
Other Subjects
Algorithms; Approximation theory; Biotechnology; Computational complexity; Set theory; Trees (mathematics); World Wide Web; XML; Bioinformatics; Biological databases; Generalized tree pattern (GTP); Taxonomy; Database systems
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
927.97 KB
Format
Adobe PDF
Checksum
(MD5):655a0d984338f68cae8a256c7fcc5881