JAL-2759 Moved propagateInsertions out of HiddenColumns
[jalview.git] / src / jalview / analysis / Rna.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 /* Author: Lauren Michelle Lui 
22  * Methods are based on RALEE methods http://personalpages.manchester.ac.uk/staff/sam.griffiths-jones/software/ralee/
23  * Additional Author: Jan Engelhart (2011) - Structure consensus and bug fixing
24  * Additional Author: Anne Menard (2012) - Pseudoknot support and secondary structure consensus
25  * */
26
27 package jalview.analysis;
28
29 import jalview.analysis.SecStrConsensus.SimpleBP;
30 import jalview.datamodel.SequenceFeature;
31 import jalview.util.MessageManager;
32
33 import java.util.ArrayList;
34 import java.util.HashMap;
35 import java.util.Hashtable;
36 import java.util.List;
37 import java.util.Map;
38 import java.util.Stack;
39
40 public class Rna
41 {
42
43   /**
44    * Answers true if the character is a valid open pair rna secondary structure
45    * symbol. Currently accepts A-Z, ([{<
46    * 
47    * @param c
48    * @return
49    */
50   public static boolean isOpeningParenthesis(char c)
51   {
52     return ('A' <= c && c <= 'Z' || c == '(' || c == '[' || c == '{'
53             || c == '<');
54   }
55
56   /**
57    * Answers true if the string is a valid open pair rna secondary structure
58    * symbol. Currently accepts A-Z, ([{<
59    * 
60    * @param s
61    * @return
62    */
63   public static boolean isOpeningParenthesis(String s)
64   {
65     return s != null && s.length() == 1
66             && isOpeningParenthesis(s.charAt(0));
67   }
68
69   /**
70    * Answers true if the character is a valid close pair rna secondary structure
71    * symbol. Currently accepts a-z, )]}>
72    * 
73    * @param c
74    * @return
75    */
76   public static boolean isClosingParenthesis(char c)
77   {
78     return ('a' <= c && c <= 'z' || c == ')' || c == ']' || c == '}'
79             || c == '>');
80   }
81
82   /**
83    * Answers true if the string is a valid close pair rna secondary structure
84    * symbol. Currently accepts a-z, )]}>
85    * 
86    * @param s
87    * @return
88    */
89   public static boolean isClosingParenthesis(String s)
90   {
91     return s != null && s.length() == 1
92             && isClosingParenthesis(s.charAt(0));
93   }
94
95   /**
96    * Returns the matching open pair symbol for the given closing symbol.
97    * Currently returns A-Z for a-z, or ([{< for )]}>, or the input symbol if it
98    * is not a valid closing symbol.
99    * 
100    * @param c
101    * @return
102    */
103   public static char getMatchingOpeningParenthesis(char c)
104   {
105     if ('a' <= c && c <= 'z')
106     {
107       return (char) (c + 'A' - 'a');
108     }
109     switch (c)
110     {
111     case ')':
112       return '(';
113     case ']':
114       return '[';
115     case '}':
116       return '{';
117     case '>':
118       return '<';
119     default:
120       return c;
121     }
122   }
123
124   /**
125    * Based off of RALEE code ralee-get-base-pairs. Keeps track of open bracket
126    * positions in "stack" vector. When a close bracket is reached, pair this
127    * with the last matching element in the "stack" vector and store in "pairs"
128    * vector. Remove last element in the "stack" vector. Continue in this manner
129    * until the whole string is processed. Parse errors are thrown as exceptions
130    * wrapping the error location - position of the first unmatched closing
131    * bracket, or string length if there is an unmatched opening bracket.
132    * 
133    * @param line
134    *          Secondary structure line of an RNA Stockholm file
135    * @return
136    * @throw {@link WUSSParseException}
137    */
138   protected static List<SimpleBP> getSimpleBPs(CharSequence line)
139           throws WUSSParseException
140   {
141     Hashtable<Character, Stack<Integer>> stacks = new Hashtable<Character, Stack<Integer>>();
142     List<SimpleBP> pairs = new ArrayList<SimpleBP>();
143     int i = 0;
144     while (i < line.length())
145     {
146       char base = line.charAt(i);
147
148       if (isOpeningParenthesis(base))
149       {
150         if (!stacks.containsKey(base))
151         {
152           stacks.put(base, new Stack<Integer>());
153         }
154         stacks.get(base).push(i);
155
156       }
157       else if (isClosingParenthesis(base))
158       {
159
160         char opening = getMatchingOpeningParenthesis(base);
161
162         if (!stacks.containsKey(opening))
163         {
164           throw new WUSSParseException(MessageManager.formatMessage(
165                   "exception.mismatched_unseen_closing_char", new String[]
166                   { String.valueOf(base) }), i);
167         }
168
169         Stack<Integer> stack = stacks.get(opening);
170         if (stack.isEmpty())
171         {
172           // error whilst parsing i'th position. pass back
173           throw new WUSSParseException(MessageManager.formatMessage(
174                   "exception.mismatched_closing_char", new String[]
175                   { String.valueOf(base) }), i);
176         }
177         int temp = stack.pop();
178
179         pairs.add(new SimpleBP(temp, i));
180       }
181       i++;
182     }
183     for (char opening : stacks.keySet())
184     {
185       Stack<Integer> stack = stacks.get(opening);
186       if (!stack.empty())
187       {
188         /*
189          * we have an unmatched opening bracket; report error as at
190          * i (length of input string)
191          */
192         throw new WUSSParseException(MessageManager.formatMessage(
193                 "exception.mismatched_opening_char", new String[]
194                 { String.valueOf(opening), String.valueOf(stack.pop()) }),
195                 i);
196       }
197     }
198     return pairs;
199   }
200
201   
202
203   
204
205   /**
206    * Function to get the end position corresponding to a given start position
207    * 
208    * @param indice
209    *          - start position of a base pair
210    * @return - end position of a base pair
211    */
212   /*
213    * makes no sense at the moment :( public int findEnd(int indice){ //TODO:
214    * Probably extend this to find the start to a given end? //could be done by
215    * putting everything twice to the hash ArrayList<Integer> pair = new
216    * ArrayList<Integer>(); return pairHash.get(indice); }
217    */
218
219   /**
220    * Answers true if the character is a recognised symbol for RNA secondary
221    * structure. Currently accepts a-z, A-Z, ()[]{}<>.
222    * 
223    * @param c
224    * @return
225    */
226   public static boolean isRnaSecondaryStructureSymbol(char c)
227   {
228     return isOpeningParenthesis(c) || isClosingParenthesis(c);
229   }
230
231   /**
232    * Answers true if the string is a recognised symbol for RNA secondary
233    * structure. Currently accepts a-z, A-Z, ()[]{}<>.
234    * 
235    * @param s
236    * @return
237    */
238   public static boolean isRnaSecondaryStructureSymbol(String s)
239   {
240     return isOpeningParenthesis(s) || isClosingParenthesis(s);
241   }
242
243   /**
244    * Translates a string to RNA secondary structure representation. Returns the
245    * string with any non-SS characters changed to spaces. Accepted characters
246    * are a-z, A-Z, and (){}[]<> brackets.
247    * 
248    * @param ssString
249    * @return
250    */
251   public static String getRNASecStrucState(String ssString)
252   {
253     if (ssString == null)
254     {
255       return null;
256     }
257     StringBuilder result = new StringBuilder(ssString.length());
258     for (int i = 0; i < ssString.length(); i++)
259     {
260       char c = ssString.charAt(i);
261       result.append(isRnaSecondaryStructureSymbol(c) ? c : " ");
262     }
263     return result.toString();
264   }
265
266   /**
267    * Answers true if the base-pair is either a Watson-Crick (A:T/U, C:G) or a
268    * wobble (G:T/U) pair (either way round), else false
269    * 
270    * @param first
271    * @param second
272    * @return
273    */
274   public static boolean isCanonicalOrWobblePair(char first, char second)
275   {
276     if (first > 'Z')
277     {
278       first -= 32;
279     }
280     if (second > 'Z')
281     {
282       second -= 32;
283     }
284
285     switch (first)
286     {
287     case 'A':
288       switch (second)
289       {
290       case 'T':
291       case 'U':
292         return true;
293       }
294       break;
295     case 'C':
296       switch (second)
297       {
298       case 'G':
299         return true;
300       }
301       break;
302     case 'T':
303     case 'U':
304       switch (second)
305       {
306       case 'A':
307       case 'G':
308         return true;
309       }
310       break;
311     case 'G':
312       switch (second)
313       {
314       case 'C':
315       case 'T':
316       case 'U':
317         return true;
318       }
319       break;
320     }
321     return false;
322   }
323
324   /**
325    * Answers true if the base-pair is Watson-Crick - (A:T/U or C:G, either way
326    * round), else false
327    * 
328    * @param first
329    * @param second
330    * @return
331    */
332   public static boolean isCanonicalPair(char first, char second)
333   {
334
335     if (first > 'Z')
336     {
337       first -= 32;
338     }
339     if (second > 'Z')
340     {
341       second -= 32;
342     }
343
344     switch (first)
345     {
346     case 'A':
347       switch (second)
348       {
349       case 'T':
350       case 'U':
351         return true;
352       }
353       break;
354     case 'G':
355       switch (second)
356       {
357       case 'C':
358         return true;
359       }
360       break;
361     case 'C':
362       switch (second)
363       {
364       case 'G':
365         return true;
366       }
367       break;
368     case 'T':
369     case 'U':
370       switch (second)
371       {
372       case 'A':
373         return true;
374       }
375       break;
376     }
377     return false;
378   }
379
380   /**
381    * Returns the matching close pair symbol for the given opening symbol.
382    * Currently returns a-z for A-Z, or )]}> for ([{<, or the input symbol if it
383    * is not a valid opening symbol.
384    * 
385    * @param c
386    * @return
387    */
388   public static char getMatchingClosingParenthesis(char c)
389   {
390     if ('A' <= c && c <= 'Z')
391     {
392       return (char) (c + 'a' - 'A');
393     }
394     switch (c)
395     {
396     case '(':
397       return ')';
398     case '[':
399       return ']';
400     case '{':
401       return '}';
402     case '<':
403       return '>';
404     default:
405       return c;
406     }
407   }
408
409   public static SequenceFeature[] getHelixMap(CharSequence rnaAnnotation)
410           throws WUSSParseException
411   {
412     List<SequenceFeature> result = new ArrayList<SequenceFeature>();
413
414     int helix = 0; // Number of helices/current helix
415     int lastopen = 0; // Position of last open bracket reviewed
416     int lastclose = 9999999; // Position of last close bracket reviewed
417
418     Map<Integer, Integer> helices = new HashMap<Integer, Integer>();
419     // Keep track of helix number for each position
420
421     // Go through each base pair and assign positions a helix
422     List<SimpleBP> bps = getSimpleBPs(rnaAnnotation);
423     for (SimpleBP basePair : bps)
424     {
425       final int open = basePair.getBP5();
426       final int close = basePair.getBP3();
427
428       // System.out.println("open " + open + " close " + close);
429       // System.out.println("lastclose " + lastclose + " lastopen " + lastopen);
430
431       // we're moving from right to left based on closing pair
432       /*
433        * catch things like <<..>>..<<..>> |
434        */
435       if (open > lastclose)
436       {
437         helix++;
438       }
439
440       /*
441        * catch things like <<..<<..>>..<<..>>>> |
442        */
443       int j = bps.size() - 1;
444       while (j >= 0)
445       {
446         int popen = bps.get(j).getBP5();
447
448         // System.out.println("j " + j + " popen " + popen + " lastopen "
449         // +lastopen + " open " + open);
450         if ((popen < lastopen) && (popen > open))
451         {
452           if (helices.containsValue(popen)
453                   && ((helices.get(popen)) == helix))
454           {
455             continue;
456           }
457           else
458           {
459             helix++;
460             break;
461           }
462         }
463         j -= 1;
464       }
465
466       // Put positions and helix information into the hashtable
467       helices.put(open, helix);
468       helices.put(close, helix);
469
470       // Record helix as featuregroup
471       result.add(new SequenceFeature("RNA helix", "", open, close,
472               String.valueOf(helix)));
473
474       lastopen = open;
475       lastclose = close;
476     }
477
478     return result.toArray(new SequenceFeature[result.size()]);
479   }
480 }