Local structural alignment of RNA with affine gap model

A non-coding RNA (ncRNA) is a RNA molecule that does not translate into proteins. It has been shown to be involved in many biological processes [1‐4]. The number of ncRNAs within the human genome was underestimated before, but recently some databases reveal over 212,000 ncRNAs [5] and more than 1,300 ncRNA families [6]. Large discoveries of ncRNAs and their families show the possibilities that ncRNAs may be as diverse as protein molecules [7]. Identifying ncRNAs is an important problem in biological study. However, it is time consuming and there is no effective method to identify ncRNAs in a laboratory, predicting ncRNAs based on known ncRNAs using comparative computational approach is one of the promising directions to identify potential candidates for further verification.

Most of the computational approaches are based on the observation that if two different ncRNA molecules are in the same family (with similar biological functions), they usually exhibit similar sequences as well as secondary structures. One common approach [8‐10] is as follows. We pick an ncRNA member of a family with known sequence and secondary structure (referred as the query), scan along a genomic sequence and for each possible region (referred as the target), perform an alignment between the query and the target to obtain a similarity measure to decide if the region is a potential ncRNA candidate for that family. The similarity measure may only base on the sequence or both the sequence and secondary structure (the latter case is referred as structural alignment). Along this direction, there are some approaches [11‐14] that make use of secondary structure prediction tools to predict the secondary structure to be formed by the target assuming that it is an ncRNA before performing the alignment. The accuracy may, however, depend on the accuracy of the secondary structure prediction tools.

Instead of using one member of a family, some other approaches [15] use a set of ncRNAs from the same family to train a model (e.g. covariance model). Then, using this model to scan a genomic sequence to identify potential regions that are ncRNA candidates of that family. What information (sequence similarity and/or secondary structure) to be captured from the known ncRNAs depends on how we define the model. However, in some cases, we may not have enough known members in a family to train a model. In this paper, we focus on the problem that uses one known member as the query and align it with a target sequence. We remark that there are also other computational methods that identify ncRNAs without using known members in a family. For example, some try to identify ncRNAs by considering the stability of secondary structures formed by the substrings of a given genome [16]. This method may not be very effective because a random sequence with high GC composition also allows an energetically favorable secondary structure [17]. So, the comparative approach we described in the above is still one of the most popular approaches.

The core idea behind all comparative approaches is to compute the similarity between the query (known member(s)) and the target (each possible region in the genomic sequence to be investigated). Some only consider sequence similarity which may not work well for families in which members do not have high sequence similarity (e.g. members of RF00017 in Rfam 9.1 [6] only have 39% sequence similarity). For example, Gotohscan [8] considers semi-global alignment with affine gap penalty according to the sequence similarity only. For those also consider the similarity of secondary structure, they usually require the whole sequence of the query to be aligned with the whole sequence of the target (referred as global alignment in the community) [10]. However, similar to the protein sequence, the ncRNAs in the same family may not have similar sequence or structure for the whole sequence but only for the substrings of them (those supposed to be the functional parts), especially when they belong to species with long evolutionary distance apart. Figure 1 shows one of these examples. It shows the multiple sequence alignment between some members of the family RF01051 in Rfam 9.1 database. The two circled members (i.e. AAUO01000012 and AAXYO1000014) are not quite similar if we consider the global alignment. Also, for the subregions that they look similar (i.e. the circled region), there exist large insertion/deletion (gaps). There are also evidences that gaps may be common in ncRNA homologs [18]. Considering local structural alignment with gap model seems to be more appropriate for predicting new members for some ncRNA families. [9] consider some restricted cases of local alignment according to the query structure. Another work that also consider local alignment is [11], but they cannot handle gaps.

We consider the following problem. Given a query sequence together with its secondary structure, we try to identify the substring in the given target sequence (with unknown secondary structure) that can align to a substring in the query sequence with the highest structural similarity score based on the affine gap model (see next section for formal definitions). We assume that the secondary structures of the ncRNAs are regular, that is, they do not have pseudoknots (no two base pairs crossing each other). This type of ncRNAs is found to be the most abundant in existing databases. We consider all possible substrings of the query sequence, even for those substrings that cover only one of the end points of some base pairs in the structure.

An ncRNA molecule can be regarded as a sequence of four characters {A, C, G, U}, each character is referred as a base. Some of these bases may form pairs (linked up by a hydrogen bond) with some restrictions such as each base can only pair up with at most one other base and only complementary bases can form a pair (e.g. (A, U), (C, G), (U,G)). The set of base pairs formed by the molecule is referred as its secondary structure.

Formally speaking, let S = s₁s₂ … s _m be a length-m ncRNA sequence where s _i ∈ {A, C, G, U} for 1 ≤ i ≤ m and M be the secondary structure of S. M is represented as a set of base pair positions. i.e. M = {(i, j)|1 ≤ i <j ≤ m, (s _i , s _j ) is a base pair}. If (s _i , s _j ) is base pair, then (s _i , s _j ) ∈ {(A, U), (C, G), (G, C), (G, U), (U, A), (U, G)}. Let M _x,y ⊆ M be the set of base pairs within the subsequence s _x s _{x +1}…s _y , 1 ≤ x <y ≤ m, i.e., M _x,y = {(i, j) ∈ M|x ≤ i <j ≤ y}. Note that if (i, j) ∈ M and only i or j inside the region [x…y], then (i, j) ∉ M _x,y . We assume that there is no two base pairs sharing the same position, i.e., for any (i₁, j₁), (i₂, j₂) ∈ M, i₁ ≠ j₂, i₂ ≠ j₁, and i₁ = i₂ if and only if j₁ = j₂.

A regular structure is the structure in which there does not exist any two base pairs crossing each other. The formal definition is as follows:

Definition 1 M _x,y is a regular structure if there does not exist two base pairs (i, j), (k, l) ∈ M _x,y such that i <k <j <l or k <i <l <j.

Note that an empty set is also considered as a regular structure.

The details of the algorithm for solving the problem will be given in Method Section. In this section, we evaluate the resulting algorithm and show that considering local structural alignment with affine gap model can improve the effectiveness of locating ncRNAs for the families in which members may have variable size of hairpins, loops or stems when compared to using global alignment [10], local alignment without gap penalty model and Gotohscan [8]. Note that the differences in size of hairpins, loops or stems represent gaps in the corresponding sequences.

To test the algorithm, we selected around twenty ncRNA families in which the members have variable sizes of hairpins, loops or stems. We construct our testing cases based on real ncRNAs as follows. For each family, we first select a seed member (i.e. In Rfam database, there is a set of reliable members which are regarded as seed members) as the query sequence Q. To demonstrate the effectiveness of the affine gap model, we select the longest seed member as this query sequence. We then created a long random sequence with even distribution of four characters {A, C, G, T} to simulate a long genome. The length of this long random sequence is around ten times of the total length of all the seed members of the family. Finally, we embedded the full members (i.e. all the members including the seed members) of the family (except the one chosen as query) into this long random sequence in arbitrary positions. If there are more than 100 members, then we randomly picked 100 of them. This resulting sequence is our T.

Let l be the the maximum length of all the members of the family. For every region in T with length l+20, we compute the structural alignment score of the region and the query sequence. We use the same scoring scheme as in [9] and set the gap starting penalty (h) and gap extension penalty (s) to be 5 and 0.1, respectively. The details of the families including the sequence selected as the query, the length of the sequence, and the number of members embedded in each family are given in Table 1.

We compare our algorithm with the global structural alignment [10], local structural alignment without affine gap model and Gotohscan [8]. Gotohscan was used to locate ncRNAs candidates on Trichoplax adhaerens by using single real ncRNA as query. It was designed to check only sequence similarity with affine gap model. Since the global structural alignment software is not available, we implemented both global and local without affine gap algorithms. For Gotohscan, we downloaded the version 1.3 from the website. We assume that regions other than the members of the family are false hits as they are likely not to be members of the family. To compute the effectiveness of our method, we use the smallest threshold with no false positive and the thresholds of allowing 5% or 10% false positive rate. We assume that the method finds a real hit if the score of the region is larger than this threshold. Thus a real hit will be missed if the computed score is smaller than or equal to this threshold. Table 2 and Table 3 summarize the result when using different algorithms to locate the other ncRNA members along the genome. When the smallest threshold with no false positive is used, the average percentage of misses when using Gotohscan is 53.9%; global alignment is 18.4%; local alignment without affine gap model is 17.9%; local alignment with affine gap model is 7.2%. When the threshold of allowing 5% or 10% false positive rate is used, the results show that the local structural alignment algorithm with affine gap model also works satisfactory except for the family RF00033. Table 4 also lists the area under the ROC curve when considering the false positive rate ≤ 10%. Note that the area is normalized to the range between 0 and 1.

We also use RF00661 as an example and show the score distribution between the real hits and the false hits when using different algorithms in Figure 2. As one can see, the local structural alignment algorithm with affine gap penalty can increase the difference between the scores of real hits and the scores of false hits compared with the other methods, and so it has a higher distinguishing power to identify the real ncRNA members along the long genome sequence for these families.

Our program take around 15 seconds for performing local structural alignment with affine gap model between query and target of around 150 bases long, and around 30 seconds for 200 bases long. We tested the program on a machine with 2.4GHz dual-core CPU and 8G memory.

In the paper, we provided an algorithm to handle local structural alignment with affine gap model of RNA with regular structure that compute the optimal alignment. Our experiments show that the solution is effective for some ncRNA families in which members may have varying sizes on hairpins, loops or stems (contributing to large gaps) when compared to using only global alignment or local alignment without gap model. And also we have not yet studied different types of gap penalty model and the effect of setting different gap penalty parameters. Other interesting directions include speeding up the algorithm and considering other more complicated structures (e.g. the structures with pseudoknots). In the mean time, we have completed the algorithm of computing local structural alignment for simple pseudoknots structure, and we are now in the progress of performing experiments.

We develop a dynamic programming algorithm to solve the problem. Before we describe the method, we would like to define some variations of alignments which will be used in our algorithm. Let S[1…m] be the query sequence with known structure M and T[1…n] be the target sequence with unknown structure.

Definition 4 Optimal prefix-global structural alignment between S[1…m] and T[1…n] is to find a prefix S[1…y] where 0 ≤ y ≤ m (i.e. S is an empty string when y = 0) such that the score of the optimal global structural alignment between the prefix S[1…y] and T[1…n] is maximum.

Definition 5 Optimal suffix-global structural alignment between S[1…m] and T[1…n] is to find S[x…m] where 1 ≤ x ≤ m + 1 (i.e. S is an empty string when x = m + 1) such that the score of the optimal global structural alignment between the suffix S[x…m] and T[1…n] is maximum.

Definition 6 Optimal semi-global structural alignment between S[1…m] and T[1…n] is to find a substring S[x…y] where 1 ≤ x, y ≤ m such that the score of the optimal global structural alignment between the substring S[x…y] and T[1…n] is maximum.

Let the affine gap model be h + sL, where h is the gap opening penalty, s represents a gap extension penalty, and L denotes the length of gap. Our method consists of two steps. In the first step, we compute the optimal semi-global structural alignment between S and all possible substrings of T. In the second step, we obtain the optimal local structural alignment between S and T resulted in the first step. Define A(p, q, e, f) to be the score of the optimal semi-global structural alignment between S[p…q] and T [e…f]. The score of the optimal local structural alignment between S and T can be obtained from the entry max _{e ≤ f +1}A(1, m, e, f). We first show how to compute A, then show how to use the structure of S to guide the computation of A without considering all possible combinations of p, q.

When considering any substring S′ = S[x′…y′] of S[x…y], there are four possible cases: (1) S′ is equal to S (i.e. x′ = x, y′ = y); (2) S′ is a proper prefix in S (i.e. x′ = x, y′ <y); (3) S′ is a proper suffix in S (i.e. x′ >x, y′ = y); (4) S′ is a substring of S[x + 1…y – 1] (i.e. x′ >x, y′ <y); Therefore, we can consider each case one by one when computing the value of A.

Define A₁(p, q, e, f) to be the score of the optimal global structural alignment between S[p…q] and T[e…f]. Define A₂(p, q, e, f) to be the score of the optimal prefix-global structural alignment between S[p…q – 1] and T[e…f]. Define A₃(p, q, e, f) to be the score of the optimal suffix-global structural alignment between S[p + 1…q] and T[e…f]. Define A₄(p, q, e, f) to be the score of the optimal semi-global structural alignment between S[p + 1…q – 1] and T[e…f].

The value of A(p, q, e, f) can be computed recursively and it is the maximum value of four cases: (1) when S′ = S[p, q] (i.e. A₁(p, q, e, f)); (2) when S′ is a proper prefix of S[p, q] (i.e. A₂(p, q, e, f)); (3) when S′ is a proper suffix of S[p, q] (i.e. A₃(p, q, e, f); (4) when S′ is a substring of S[p + 1, q – 1] (i.e. A₄(p, q, e, f); Lemma 1 summarizes these cases.

Lemma 1

The following subsections describe how to compute A₁,A₂,A₃,A₄.