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 }