A Fast Algorithm for Optimal Alignment between Similar Ordered Trees

• Autorzy: Jansson J. , Lingas A.
• Języki publikacji: EN

Abstrakty

EN

We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n logn ź(maxdeg)3 źd2) time, where n = max{|S|,|T|} and maxdeg is the maximum degree of all nodes in S and T. If d is not known in advance, we can construct an optimal alignment in O(n logn ź(maxdeg)3źf2) time, where f is the difference between the highest possible score for any alignment between two trees having a total of |S| + |T| nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to O(n logn źd2) and O(n logn źf2), respectively.

Słowa kluczowe

EN

algorithm of Jiang, Wang, and Zhang; algorithm Fast Score

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 105--120
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Jansson J.

autor

Lingas A.

• Department of Computer Science, Lund University, Box 118, SE-22100 Lund, Sweden,

Bibliografia

• [1] Alstrup, S., Brodal, G., Rauhe, T.: New Data Structures for Orthogonal Range Searching, Proceedings of the 41 Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000.
• [2] Gusfield, D.: Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge University Press, 1997.
• [3] Jansson, J., Lingas, A.: A Fast Algorithm for Optimal Alignment between Similar Ordered Trees, Proceedings of the 12 Annual Symposium on Combinatorial Pattern Matching (CPM 2001), 2001.
• [4] Jiang, T., Wang, L., Zhang, K.: Alignment of trees - an alternative to tree edit, Theoretical Computer Science, 143, 1995, 137-148, A preliminary version appeared in Proceedings of the 5 Annual Symposium on Combinatorial Pattern Matching (CPM’94), pages 75-86, 1994.
• [5] Keselman, D., Amir, A.: Maximum agreement subtree in a set of evolutionary trees - metrics and efficient algorithms, Proceedings of the 35 Annual Symposium on Foundations of Computer Science (FOCS ’94), 1994.
• [6] Le, S.-Y., Nussinov, R., Maizel, J.: Tree graphs of RNA secondary structures and their comparisons, Computers and Biomedical Research, 22, 1989, 461-473.
• [7] Pevzner, P.: Computational Molecular Biology : An Algorithmic Approach, The MIT Press, Massachusetts, 2000.
• [8] Preparata, F., Shamos, M.: Computational Geometry, Springer-Verlag, New York, 1985.
• [9] Setubal, J., Meidanis, J.: Introduction to Computational Molecular Biology, PWS Publishing Company, Boston, 1997.
• [10] Shapiro, B.: An algorithm for comparing multiple RNA secondary structures, Computer Applications in the Biosciences, 4, 1988, 387-393.
• [11] Tai, K.-C.: The tree-to-tree correction problem, Journal of the ACM, 26(3), 1979, 422-433. [12] Tarjan, R., Vishkin, U.: An efficient parallel biconnectivity algorithm, SIAM Journal on Computing, 14(4), 1985, 862-874.
• [13] Waterman, M.: Introduction to Computational Biology : Maps, Sequences, and Genomes, Chapman & Hall, London, 1995.
• [14] Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, 18(6), 1989, 1245-1262.