Advanced

A fast algorithm for optimal alignment between similar ordered trees

Jansson, Jesper LU and Lingas, Andrzej LU (2003) In Fundamenta Informaticae 56(1-2). p.105-120
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) (.) d(2)) 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 .) f(2)) 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... (More)
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) (.) d(2)) 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 .) f(2)) 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 log n (.) d(2)) and O(n log n (.) f(2)), respectively. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Fundamenta Informaticae
volume
56
issue
1-2
pages
105 - 120
publisher
IOS Press
external identifiers
  • wos:000186087600007
  • scopus:0141493759
ISSN
0169-2968
project
VR 2002-4049
language
English
LU publication?
yes
id
c767ed0e-ebe6-4d2e-834a-52c95b234d6b (old id 297998)
date added to LUP
2007-08-03 10:43:24
date last changed
2018-05-29 09:43:02
@article{c767ed0e-ebe6-4d2e-834a-52c95b234d6b,
  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) (.) d(2)) 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 .) f(2)) 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 log n (.) d(2)) and O(n log n (.) f(2)), respectively.},
  author       = {Jansson, Jesper and Lingas, Andrzej},
  issn         = {0169-2968},
  language     = {eng},
  number       = {1-2},
  pages        = {105--120},
  publisher    = {IOS Press},
  series       = {Fundamenta Informaticae},
  title        = {A fast algorithm for optimal alignment between similar ordered trees},
  volume       = {56},
  year         = {2003},
}