Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

An Unambiguous And Complete Dynamic Programming Algorithm For Tree Alignment

Cedric Chauve 1 Julien Courtiel 1 Yann Ponty 1, 2, 3
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : Pairwise ordered tree alignment is an important pattern matching problem, motivated by RNA secondary structure comparison for example, that can be solved efficiently using Dynamic Programming (DP). An inquiry into the multiplicity of optimal solutions, as well as the existence of potentially interesting sub-optimal solutions, naturally motivates the question of exploring the space of all, optimal and sub-optimal, tree alignments. There are well-known DP-based techniques that allow for such an exploration, but they require completeness and unambiguity of the DP scheme, i.e. the existence of a score-preserving bijection between the search space and the set of possible derivations of the DP scheme. In this paper, we present the first unambiguous and complete dynamic programming algorithm for the alignment of a pair of ordered rooted trees. Our algorithm optimally aligns two trees of size $n_1$ and $n_2$ in $\Theta(n_1 n_2 max(n_1, n_2)^2)$ time in the worst-case scenario. Assuming uniformly-drawn random trees as input, it has average-case time and space complexities in $\Theta(n_1 n_2)$.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Yann Ponty <>
Submitted on : Thursday, May 21, 2015 - 5:25:42 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Thursday, April 20, 2017 - 5:52:47 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-01154030, version 1
  • ARXIV : 1505.05983


Cedric Chauve, Julien Courtiel, Yann Ponty. An Unambiguous And Complete Dynamic Programming Algorithm For Tree Alignment. 2015. ⟨hal-01154030v1⟩



Record views


Files downloads