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.Arrays;
  35 import java.util.HashSet;
  36 import java.util.Hashtable;
  37 import java.util.Stack;
  38 import java.util.Vector;
  39
  40 public class Rna
  41 {
  42
  43   static Hashtable<Integer, Integer> pairHash = new Hashtable();
  44
  45   private static final Character[] openingPars = { '(', '[', '{', '<', 'A',
  46       'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
  47       'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
  48
  49   private static final Character[] closingPars = { ')', ']', '}', '>', 'a',
  50       'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
  51       'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
  52
  53   private static HashSet<Character> openingParsSet = new HashSet<Character>(
  54           Arrays.asList(openingPars));
  55
  56   private static HashSet<Character> closingParsSet = new HashSet<Character>(
  57           Arrays.asList(closingPars));
  58
  59   private static Hashtable<Character, Character> closingToOpening = new Hashtable<Character, Character>()
  60   // Initializing final data structure
  61   {
  62     private static final long serialVersionUID = 1L;
  63     {
  64       for (int i = 0; i < openingPars.length; i++)
  65       {
  66         // System.out.println(closingPars[i] + "->" + openingPars[i]);
  67         put(closingPars[i], openingPars[i]);
  68       }
  69     }
  70   };
  71
  72   private static boolean isOpeningParenthesis(char c)
  73   {
  74     return openingParsSet.contains(c);
  75   }
  76
  77   private static boolean isClosingParenthesis(char c)
  78   {
  79     return closingParsSet.contains(c);
  80   }
  81
  82   private static char matchingOpeningParenthesis(char closingParenthesis)
  83           throws WUSSParseException
  84   {
  85     if (!isClosingParenthesis(closingParenthesis))
  86     {
  87       throw new WUSSParseException(
  88               MessageManager.formatMessage(
  89                       "exception.querying_matching_opening_parenthesis_for_non_closing_parenthesis",
  90                       new String[] { new StringBuffer(closingParenthesis)
  91                               .toString() }), -1);
  92     }
  93
  94     return closingToOpening.get(closingParenthesis);
  95   }
  96
  97   /**
  98    * Based off of RALEE code ralee-get-base-pairs. Keeps track of open bracket
  99    * positions in "stack" vector. When a close bracket is reached, pair this
 100    * with the last element in the "stack" vector and store in "pairs" vector.
 101    * Remove last element in the "stack" vector. Continue in this manner until
 102    * the whole string is processed.
 103    *
 104    * @param line
 105    *          Secondary structure line of an RNA Stockholm file
 106    * @return Array of SequenceFeature; type = RNA helix, begin is open base
 107    *         pair, end is close base pair
 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 = matchingOpeningParenthesis(base);
 132
 133         if (!stacks.containsKey(opening))
 134         {
 135           throw new WUSSParseException(MessageManager.formatMessage(
 136                   "exception.mismatched_unseen_closing_char",
 137                   new String[] { new StringBuffer(base).toString() }), 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[] { new StringBuffer(base).toString() }), 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         throw new WUSSParseException(MessageManager.formatMessage(
 160                 "exception.mismatched_opening_char",
 161                 new String[] { new StringBuffer(opening).toString(),
 162                     Integer.valueOf(stack.pop()).toString() }), i);
 163       }
 164     }
 165     return pairs;
 166   }
 167
 168   public static SequenceFeature[] GetBasePairs(CharSequence line)
 169           throws WUSSParseException
 170   {
 171     Vector<SimpleBP> bps = GetSimpleBPs(line);
 172     SequenceFeature[] outPairs = new SequenceFeature[bps.size()];
 173     for (int p = 0; p < bps.size(); p++)
 174     {
 175       SimpleBP bp = bps.elementAt(p);
 176       outPairs[p] = new SequenceFeature("RNA helix", "", "", bp.getBP5(),
 177               bp.getBP3(), "");
 178     }
 179     return outPairs;
 180   }
 181
 182   public static ArrayList<SimpleBP> GetModeleBP(CharSequence line)
 183           throws WUSSParseException
 184   {
 185     Vector<SimpleBP> bps = GetSimpleBPs(line);
 186     return new ArrayList<SimpleBP>(bps);
 187   }
 188
 189   /**
 190    * Function to get the end position corresponding to a given start position
 191    *
 192    * @param indice
 193    *          - start position of a base pair
 194    * @return - end position of a base pair
 195    */
 196   /*
 197    * makes no sense at the moment :( public int findEnd(int indice){ //TODO:
 198    * Probably extend this to find the start to a given end? //could be done by
 199    * putting everything twice to the hash ArrayList<Integer> pair = new
 200    * ArrayList<Integer>(); return pairHash.get(indice); }
 201    */
 202
 203   /**
 204    * Figures out which helix each position belongs to and stores the helix
 205    * number in the 'featureGroup' member of a SequenceFeature Based off of RALEE
 206    * code ralee-helix-map.
 207    *
 208    * @param pairs
 209    *          Array of SequenceFeature (output from Rna.GetBasePairs)
 210    */
 211   public static void HelixMap(SequenceFeature[] pairs)
 212   {
 213
 214     int helix = 0; // Number of helices/current helix
 215     int lastopen = 0; // Position of last open bracket reviewed
 216     int lastclose = 9999999; // Position of last close bracket reviewed
 217     int i = pairs.length; // Number of pairs
 218
 219     int open; // Position of an open bracket under review
 220     int close; // Position of a close bracket under review
 221     int j; // Counter
 222
 223     Hashtable helices = new Hashtable(); // Keep track of helix number for each
 224                                          // position
 225
 226     // Go through each base pair and assign positions a helix
 227     for (i = 0; i < pairs.length; i++)
 228     {
 229
 230       open = pairs[i].getBegin();
 231       close = pairs[i].getEnd();
 232
 233       // System.out.println("open " + open + " close " + close);
 234       // System.out.println("lastclose " + lastclose + " lastopen " + lastopen);
 235
 236       // we're moving from right to left based on closing pair
 237       /*
 238        * catch things like <<..>>..<<..>> |
 239        */
 240       if (open > lastclose)
 241       {
 242         helix++;
 243       }
 244
 245       /*
 246        * catch things like <<..<<..>>..<<..>>>> |
 247        */
 248       j = pairs.length - 1;
 249       while (j >= 0)
 250       {
 251         int popen = pairs[j].getBegin();
 252
 253         // System.out.println("j " + j + " popen " + popen + " lastopen "
 254         // +lastopen + " open " + open);
 255         if ((popen < lastopen) && (popen > open))
 256         {
 257           if (helices.containsValue(popen)
 258                   && (((Integer) helices.get(popen)) == helix))
 259           {
 260             continue;
 261           }
 262           else
 263           {
 264             helix++;
 265             break;
 266           }
 267         }
 268
 269         j -= 1;
 270       }
 271
 272       // Put positions and helix information into the hashtable
 273       helices.put(open, helix);
 274       helices.put(close, helix);
 275
 276       // Record helix as featuregroup
 277       pairs[i].setFeatureGroup(Integer.toString(helix));
 278
 279       lastopen = open;
 280       lastclose = close;
 281
 282     }
 283   }
 284 }