A Fast Algorithm for Optimal Alignment between Similar Ordered Trees

Jesper Andreas Jansson, Andrzej Lingas

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)

Abstract

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 log n · (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 log n · (maxdeg)3 · f2) time, where/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 log n · d2) and O(n log n · f2), respectively.
Original languageEnglish
Pages (from-to)105-120
Number of pages16
JournalFundamenta Informaticae
Volume56
Issue number1-2
Publication statusPublished - 1 Jul 2003
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Cite this