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