1 Introduction

Noncoding RNA (ncRNA) plays an important role in a variety of biological processes, including RNA modification, gene regulation, and choromosome replication (Frank and Pace, 1998; Luo and Zhou, 2001; Mitchels and Bensaude, 2001). In general, the biological functions of ncRNA are determined by its secondary structure. Recently, due to the large amount of available genome data, computational approaches have been developed to search genomes to identify new ncRNAs (Jones and Eddy, 2001; Lowe and Eddy, 1997). Most of these approaches use a structure model to describe the secondary structure of an ncRNA family and use sequence-structure alignment to determine whether a given sequence segment belongs to the ncRNA family.

Most software tools (Lowe and Eddy, 1997; Klein and Eddy, 2003) that can search genomes for ncRNAs use the covariance model (CM) (Eddy and Durbin, 1994) to model the secondary structure of an ncRNA family. Similar to the Hidden Markov model (HMM), CM uses the statistical profiles of all single and paired positions in the sequence to describe both the primary sequence and the secondary structure of an ncRNA family. The sequence-structure alignment between a sequence and a structure model can be performed by a dynamic programming algorithm (Eddy and Durbin, 1994). Based on the statistical profiles of single and paired positions, the algorithm can find the alignment with the maximum probability. The value of this probability is then used to decide whether the sequence is part of the family. The CM-based sequence structure alignment has been successfully used to identify a variety of ncRNAs in the genomes of many species.

The dynamic programming algorithm that can optimally align a sequence to a CM needs a computation time of O(WN³), where N is the number of nucleotides in the sequence and W is the size of the CM. The size of the CM is often proportional to the length of the sequences in the ncRNA family that it models. When the length of the sequence is long, CM-based searching becomes inefficient due to the time complexity needed to perform the sequence-structure alignment and the size of the genome. For example, a genome of moderate size contains around one million nucleotides and the annotation of an ncRNA that contains 300 nucleotides in such a genome may need a few days of computation time.

In this chapter, we develop a new model to describe the secondary structure of an ncRNA molecule. In particular, based on the length distribution of a structure unit in the secondary structure, we restrict the number of insertions and deletions that may occur in the structure unit during the evolution. We show that the computation time needed to align a sequence to this new model can be significantly reduced. The increase in speed that can be achieved by our model is significant for sequences that contain a large number of nucleotides.

We implemented this approach using a computer program and tested its performance in searching a few ncRNAs in genomes. We compared both the accuracy and computational efficiency of our approach with those of the CM-based search. The testing results showed that our approach can achieve search accuracy comparable with that of the CM-based search, while significantly reducing the amount of computation time needed to search through a genome.

3 Test results

We performed experiments to test the accuracy and efficiency of our approach and compared the performance of our approach with that of the conventional CM. The training data were obtained from the Rfam database. For each family, we chose up to 60 sequences, with their pairwise identities lower than 80% of the total number of nucleotides in each sequence. We inserted several RNA sequences from the same family into a random background generated with the same base composition as the sequences in the family. We then used both our algorithm and a CM-based searching algorithm to search for the inserted sequences.

In order to compute the length restrictions for each structure unit, we assumed that the lengths of each structure unit form a normal distribution and choose a confidence value of p = 0.01. The value of constant c, thus, is 3.0. We compared the sensitivity and specificity of both approaches used with several different RNA families, and the results are shown in Table 23.1. It is not difficult to see from this table that the search accuracy of our approach is comparable to that of the CM-based searching algorithm in terms of sensitivity and specificity. Table 23.2 compares the computation time of our approach with that of the CM-based search algorithm. It is not difficult to see that our approach is significantly faster than the CM-based approach for all tested ncRNA families. In particular, our approach only needs around 1.1% of the computation time needed by the CM-based search algorithm to search for Lin_4, while achieving the same search accuracy in terms of sensitivity and specificity.

4 Conclusions

In this chapter, we developed a new structure model that can be used to significantly speed up the sequence-structure alignment for ncRNAs. This new model is based on the conventional CM, which describes the sequences of an ncRNA family and their secondary structure with a statistical model. In addition to employing a CM to describe the primary sequence content and the secondary structure of sequences in an ncRNA family. Our model imposes length restrictions on each structure unit in the secondary structure. Using the length restrictions of structure units, the dynamic programming algorithm for sequence-structure alignment is significantly faster than that of the conventional CM. We showed that the length restrictions of a structure unit can be computed from the training data based on a statistical confidence value. Our testing results showed that this approach can significantly speed up the search of ncRNAs in genomes while achieving a search accuracy comparable to that of the conventional CM-based approach.

One disadvantage of our approach is that it cannot be used to model the ncRNA family, where some sequences do not contain certain structure units that are present in other sequences. In other words, some structure units are missing in these sequences. Although a missing structure unit can be accurately modeled by a conventional CM, our model may have difficulty doing that. The difficulty is largely because a missing structure unit can generate a sudden change in the range of lengths for some states in the CM. This sudden change cannot be accurately described by the length restrictions without significantly increasing the amount of computation time. The development of new approaches or models that can also handle the missing structure units is one of the directions we are taking in our future work.

So far, our approach has been used only to search for ncRNAs that do not contain pseudoknots. Pseudoknots contain crossing stems and are more difficult to model than secondary structure that does not contain crossing stems. Our previous work (Song et al., 2006; Song and Chi, 2015; Song et al., to come, 2014) has developed methods and models that can estimate the parameters associated with structural models and search for ncRNAs that contain pseudoknots. Our future may extend this approach to modeling ncRNAs that contain pseudoknot structures. In addition, approaches based on data mining and statistical principles (Qu et al., 2007, 2008, 2009; Qu and Arabnia, 2005a, 2005b; Song et al., 2014; Song and Qu, 2014) have been proved to be effective for solving problems from a large number of areas. Combining our techniques with the techniques that are already available in these areas to further improve the accuracy of our approach is another possible direction for our future work.