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