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