Identifying consensus of trees through alignment

In this paper we present a dynamic programming algorithm for identifying the similar consensus (SC) (or the largest approximately common substructures) of two ordered labeled trees based on the alignment distance. We consider a substructure of a tree T to be a connected subgraph of T. Given two trees T₁, T₂ and an integer d, the SC problem is to find a substructure U₁ of T₁ and a substructure U₂ of T₂ such that U₁ is within distance d of U₂ and where there does not exist any other substructure V₁ of T₁ and V₂ of T₂ such that V₁ and V₂ satisfy the distance constraint and the sum of the sizes of V₁ and V₂ is greater than the sum of the sizes of U₁ and U₂. The proposed algorithm solves the SC problem in time O(d² × |T₁| × |T₂| × (G₁ + G₂)²), where |T_i|, i = 1, 2, is the size of tree T_i and G_i is the maximum degree of T_i. This is as fast as the best known algorithm for aligning two ordered labeled trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to characterizing the conformation space of RNA sequences pertaining to the poliovirus, human rhinovirus and coxsackievirus, where the RNA structures are represented by ordered labeled trees.