Bijections Among Linear Trees, Lattice Walks And Rna Base-Point Mutations

Abstract

The combinatorics of RNA is one of the main mathematical tools used for RNA sequence analysis. In 1994 Schmitt and Waterman established an explicit bijection between RNA secondary structures and a certain subclass of linear trees. Later in 1997, Nkwanta established an explicit bijection between RNA secondary structures and a certain subclass of lattice walks. This thesis establishes a number of new explicit bijections involving certain subclasses of linear trees and lattice walks. It was shown by Nkwanta in 1997 that the leftmost column of the RNA triangular array counts all possible RNA secondary structures. However, there had been no known combinatorial interpretation related to RNA for the other columns of the array. In this thesis we indeed prove that the complete RNA array can be interpreted as k base-point mutations of an RNA secondary structure of length . In addition, we establish an explicit bijection between these structures and the subclass of lattice walks counted by the RNA triangular array.