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 metadatas

https://hal.inria.fr/hal-01154030
Contributor : Yann Ponty <>
Submitted on : Thursday, May 21, 2015 - 5:25:42 PM
Last modification on : Monday, December 9, 2019 - 5:24:07 PM
Long-term archiving on: Thursday, April 20, 2017 - 5:52:47 AM

Files

spire2015_draft.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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

Citation

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

Share

Metrics

Record views

140

Files downloads

71