Comparing RNA Secondary Structures Based on LZ Complexity

In this paper, we propose a new similarity measure to compare RNA secondary structure. We first transform an RNA secondary structure into three characteristic sequences. Then, based on these characteristic sequences, we calculate their LZ complexity. Finally, we obtain the similarity/dissimilarity matrix based on the LZ complexity, and make a comparison for the secondary structures at the 3′-terminus belonging to nine different species. The proposed method does not require multiple alignments and is easy to operate. This method will also be useful to researchers who are interested in evolutionary analysis.