A fast algorithm for optimal alignment between similar ordered trees
(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:
https://lup.lub.lu.se/record/297998
- author
- Jansson, Jesper LU and Lingas, Andrzej LU
- organization
- publishing date
- 2003
- 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
- 2016-04-01 15:31:27
- date last changed
- 2022-04-14 22:35:21
@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}},
}