ParaRNA: Computing Parametric Alignment of Two RNA Structures

General Description:

 ParaRNA is a software for computing parametric alignment of two RNA structures. It takes two RNA secondary structures and match score, indel score, the range of mismatch score and the range of gap score as its input, and computes all the optimal alignments in the parametric space given by mismatch score and gap score, and show them in a graphic interface. ¡¡ Nucleotide (also called base) is one of {A,U,G,C}, and a base pair is two paired nucleotides. A RNA structure is constituted by R and P, where R is a sequence of nucleotides and P is a set of base pairs. So we can express a RNA secondary structure like this: R=AAGUCUAGGUCUCACU, P={(1,5),(2,4),(7,12),(8,10),(13,15)}.(We use the position of the nucleotide in R to delegate the nucleotide and its position is numbered from 0.) For convenience, we use three integers to express a stem (which is nested pairs and among these pairs there is no other base): the first integer represents the left-end base of the stem, the second integer represents the right-end base of the stem and the last integer expresses the number of pairs in the stem. So we can express the above RNA secondary structure like this: R=AAGUCUAGGUCUCACU,P=1 5 2 7 12 1 8 10 1 13 15 1. ¡¡

In our software, we input the RNA secondary structure like the following examples:

5Srna-b_B.sub_matured_RCS
GCTTGGCGGC GTCCTACTCT CACAGGGGGA AACCCCCGAC TACCATCGGC GCTGAAGAGC
TTAACTTCCG TGTTCGGTAT GGGAACGGGT GTGACCTCTT CGCTATCGCC ACCAAA
>
>
(1  )      1       115     10
(2  )     12        48     11
(3  )     24        36      5
(4  )     50       102     2
(5  )     53       100     6
(6  )     63         89     2
(7  )     67        87      4
>

5Srna+b_B.sub_matured
TTTGGTGGCG AUAGCGAAGA GGTCACACCC GTTCCCATAC CGAACACGGA AGTTAAGCTC
TTCAGCGCCG ATGGTAGTCG GGGGTTTCCC CCTGTGAGAG TAGGACGCCG CCAAGC
>
>
(1  )      0       114     10
(2  )     13        65      2
(3  )     15        62      6
(4  )     26        52      2
(5  )     28        48      4
(6  )     67       103    11
(7  )     79        91      5
>

and give the output as follows:

The first RNA secondary structure is:

GCTTGGCGGCGTCCTACTCTCACAGGGGGAAACCCCCGACTACCATCGGCGCTGAAGAGCTTAACTTCCGTGTTCGGTATGGGAACGGGTGTGACCTCTTCGCTATCGCCACCAAA
1 115 10 12 48 11 24 36 5 50 102 2 53 100 6 63 89 2 67 87 4

The second RNA secondary structure is:

TTTGGTGGCGAUAGCGAAGAGGTCACACCCGTTCCCATACCGAACACGGAAGTTAAGCTCTTCAGCGCCGATGGTAGTCGGGGGTTTCCCCCTGTGAGAGTAGGACGCCGCCAAGC
0 114 10 13 65 2 15 62 6 26 52 2 28 48 4 67 103 11 79 91 5

Match score is:1
Indel score is:0.500
Mismatch score range is [ 0 , 2 ]
Gap score range is [ 0 , 2 ]

There are 5 optimal alignments in parametric space:

The 1 optimal alignment is:
Match Number:14
Mismatch Number:6
Indel Number:32
Gap Number:18
Pair Match Number:22
Pair Mismatch Number:2
Pair Indel Number:32

G|C|T|T|G|G|C|G|G|C|G|T|C|C|T|A|C|T|C|T|C|A|C|A|G|G|G|G|G|A|A|A|C|C|C|C|C|G|A|C|T|A|C|C|A|T|C|G|G|C|G|C|T|G|A|A|G|A|G|C|T|T|A|_|A|C|T|T|C|C|G|T|G|T|T|C|_|_|_|G|G|T|A|_|_|T|G|G|G|A|_|_|A|C|G|G|_|_|G|T|G|T|G|A|C|C|T|C|T|T|C|_|G|C|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|T|A|T|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|C|G|C|C|A|C|C|A|A|A|_|
_|T|T|T|G|G|T|G|G|C|G|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|U|A|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|G|C|_|G|A|A|G|A|G|G|T|C|A|C|A|C|_|_|C|C|G|T|_|_|T|C|C|C|A|_|_|T|A|C|C|_|_|_|G|A|A|C|A|C|G|G|A|A|G|T|_|T|A|A|G|C|T|C|T|T|C|A|G|C|G|C|C|G|A|T|G|G|T|A|G|T|C|G|G|G|G|G|T|T|T|C|C|C|C|C|T|G|T|G|A|G|A|G|T|A|G|G|A|C|G|C|C|G|C|C|A|A|G|C|

The 2 optimal alignment is:
Match Number:10
Mismatch Number:17
Indel Number:18
Gap Number:12
Pair Match Number:22
Pair Mismatch Number:2
Pair Indel Number:32

G|C|T|T|G|G|C|G|G|C|G|T|C|C|T|A|C|T|C|T|C|A|C|A|G|G|G|G|G|A|A|A|C|C|C|C|C|G|A|C|T|A|C|C|A|T|C|G|G|C|G|C|T|G|A|A|G|A|G|C|T|T|A|_|A|C|T|T|C|C|G|T|G|T|T|C|G|G|T|A|T|G|G|G|A|A|C|G|G|_|_|G|T|G|T|G|A|C|C|T|C|T|T|C|_|G|C|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|T|A|T|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|C|G|C|C|A|C|C|A|A|A|_|
_|T|T|T|G|G|T|G|G|C|G|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|U|A|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|G|C|_|G|A|A|G|A|G|G|T|C|A|C|A|C|_|_|C|C|G|T|T|C|C|C|A|T|A|C|C|G|A|A|C|A|C|G|G|A|A|G|T|_|T|A|A|G|C|T|C|T|T|C|A|G|C|G|C|C|G|A|T|G|G|T|A|G|T|C|G|G|G|G|G|T|T|T|C|C|C|C|C|T|G|T|G|A|G|A|G|T|A|G|G|A|C|G|C|C|G|C|C|A|A|G|C|

The 3 optimal alignment is:
Match Number:14
Mismatch Number:12
Indel Number:20
Gap Number:14
Pair Match Number:22
Pair Mismatch Number:2
Pair Indel Number:32

G|C|T|T|G|G|C|G|G|C|G|T|C|C|T|A|C|T|C|T|C|A|C|A|G|G|G|G|G|A|A|A|C|C|C|C|C|G|A|C|T|A|C|C|A|T|C|G|G|C|G|C|T|G|A|A|G|A|G|C|T|T|A|_|A|C|T|T|C|C|G|T|G|T|T|C|G|G|T|A|T|G|G|G|A|_|A|C|G|G|_|_|G|T|G|T|G|A|C|C|T|C|T|T|C|_|G|C|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|T|A|T|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|C|G|C|C|A|C|C|A|A|A|_|
_|T|T|T|G|G|T|G|G|C|G|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|U|A|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|G|C|_|G|A|A|G|A|G|G|T|C|A|C|A|C|_|_|C|C|G|T|_|T|C|C|C|A|T|A|C|C|G|A|A|C|A|C|G|G|A|A|G|T|_|T|A|A|G|C|T|C|T|T|C|A|G|C|G|C|C|G|A|T|G|G|T|A|G|T|C|G|G|G|G|G|T|T|T|C|C|C|C|C|T|G|T|G|A|G|A|G|T|A|G|G|A|C|G|C|C|G|C|C|A|A|G|C|

The 4 optimal alignment is:
Match Number:14
Mismatch Number:0
Indel Number:44
Gap Number:26
Pair Match Number:22
Pair Mismatch Number:1
Pair Indel Number:34

G|C|_|T|T|G|G|C|G|G|C|G|T|C|C|T|A|C|T|C|T|C|A|C|A|G|G|G|G|G|A|A|_|A|C|C|C|C|C|G|A|C|T|A|C|C|A|T|C|G|G|C|G|C|T|G|A|A|G|A|G|_|_|C|T|T|A|_|A|C|T|T|C|C|G|T|G|T|T|C|_|_|_|G|G|T|A|_|_|T|G|G|G|A|_|_|A|C|G|G|_|_|G|T|G|T|_|_|G|A|C|C|T|C|T|T|C|_|G|C|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|T|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|T|C|G|C|C|A|C|C|A|A|A|_|_|
_|_|T|T|T|G|G|T|G|G|C|G|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|U|A|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|G|C|_|G|A|A|G|A|G|G|T|C|_|_|A|C|A|C|_|_|C|C|G|T|_|_|T|C|C|C|A|_|_|T|A|C|C|_|_|_|G|A|A|C|A|C|G|G|A|A|G|T|_|T|A|A|G|_|_|C|T|C|T|T|C|A|G|C|G|C|C|G|A|T|G|G|T|A|G|T|C|G|G|G|G|G|T|T|T|C|C|C|C|C|T|G|T|G|A|G|A|G|T|A|G|G|A|_|C|G|C|C|G|C|C|A|A|_|G|C|

The 5 optimal alignment is:
Match Number:14
Mismatch Number:0
Indel Number:44
Gap Number:30
Pair Match Number:22
Pair Mismatch Number:0
Pair Indel Number:36

G|C|_|T|T|G|G|C|_|G|G|C|G|T|C|C|T|A|C|T|C|T|C|A|C|A|G|G|G|G|G|A|_|A|A|C|C|C|C|C|G|A|C|T|A|C|C|A|T|C|G|G|C|G|C|T|G|A|A|G|A|G|_|_|C|T|T|A|_|A|C|T|T|C|C|G|T|G|T|_|_|_|_|T|_|_|C|G|G|T|A|T|G|G|G|A|_|A|C|G|G|_|_|G|T|G|T|_|_|G|A|C|C|T|C|T|T|C|_|G|C|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|T|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|T|C|G|C|C|_|A|C|C|A|A|A|_|_|
_|_|T|T|T|G|G|_|T|G|G|C|G|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|A|U|A|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|G|C|_|G|A|A|G|A|G|G|T|C|_|_|A|C|A|C|_|_|C|C|G|T|_|T|C|C|C|A|T|A|C|C|G|_|_|A|_|_|_|_|A|C|A|C|G|G|A|A|G|T|_|T|A|A|G|_|_|C|T|C|T|T|C|A|G|C|G|C|C|G|A|T|G|G|T|A|G|T|C|G|G|G|G|G|T|T|T|C|C|C|C|C|T|G|T|G|A|G|A|G|T|A|G|G|A|_|C|G|C|C|G|_|C|C|A|A|_|G|C|

It is free for non-commercial use subject to copyright restrictions.