# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### A fast algorithm for optimal alignment between similar ordered trees

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)
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)
2016-04-01 15:31:27
date last changed
2020-01-12 18:32:45
```@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},
}

```