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