A simple method for finding structurally similar RNAS using two-dimensional discrete convolution

As many noncoding RNA (ncRNA) families have well-conserved secondary structures, it is important to consider structural similarity when searching for RNA homologues. However, algorithms for detecting structural similarity tend to have high computational costs, making them unsuitable for large-scale genome screening. In this paper, we introduce a simple method that can find structurally similar RNAs at a low computational cost. The method uses matched filtering of base-pair matrices to identify structurally similar RNAs in a given database. As the matched filtering involves a simple two-dimensional discrete convolution, it has a relatively low complexity of O(L²N) for any kind of RNA secondary structure, where L is the length of the target RNA and N is the number of base-pairs in the reference RNA.