srcjar/fr/orsay/lri/varna/models/templates/RNATemplate.java

   1 package fr.orsay.lri.varna.models.templates;
   2
   3 import java.awt.Point;
   4 import java.awt.geom.Point2D;
   5 import java.io.File;
   6 import java.io.IOException;
   7 import java.util.ArrayList;
   8 import java.util.Arrays;
   9 import java.util.Collection;
  10 import java.util.HashMap;
  11 import java.util.HashSet;
  12 import java.util.Hashtable;
  13 import java.util.Iterator;
  14 import java.util.LinkedList;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.NoSuchElementException;
  18 import java.util.Set;
  19 import java.util.Stack;
  20
  21 import javax.xml.parsers.DocumentBuilder;
  22 import javax.xml.parsers.DocumentBuilderFactory;
  23 import javax.xml.parsers.ParserConfigurationException;
  24 import javax.xml.transform.OutputKeys;
  25 import javax.xml.transform.Result;
  26 import javax.xml.transform.Source;
  27 import javax.xml.transform.Transformer;
  28 import javax.xml.transform.TransformerConfigurationException;
  29 import javax.xml.transform.TransformerException;
  30 import javax.xml.transform.TransformerFactory;
  31 import javax.xml.transform.TransformerFactoryConfigurationError;
  32 import javax.xml.transform.dom.DOMSource;
  33 import javax.xml.transform.stream.StreamResult;
  34
  35 import org.w3c.dom.Document;
  36 import org.w3c.dom.Element;
  37 import org.w3c.dom.Node;
  38 import org.w3c.dom.NodeList;
  39 import org.xml.sax.SAXException;
  40
  41 import fr.orsay.lri.varna.exceptions.ExceptionEdgeEndpointAlreadyConnected;
  42 import fr.orsay.lri.varna.exceptions.ExceptionFileFormatOrSyntax;
  43 import fr.orsay.lri.varna.exceptions.ExceptionInvalidRNATemplate;
  44 import fr.orsay.lri.varna.exceptions.ExceptionXMLGeneration;
  45 import fr.orsay.lri.varna.exceptions.ExceptionXmlLoading;
  46 import fr.orsay.lri.varna.models.rna.RNA;
  47 import fr.orsay.lri.varna.models.templates.RNATemplate.RNATemplateElement.EdgeEndPoint;
  48 import fr.orsay.lri.varna.models.treealign.Tree;
  49
  50
  51 /**
  52  * A model for RNA templates.
  53  * A template is a way to display an RNA secondary structure.
  54  *
  55  * @author Raphael Champeimont
  56  */
  57 public class RNATemplate {
  58         /**
  59          * The list of template elements.
  60          */
  61         private Collection<RNATemplateElement> elements = new ArrayList<RNATemplateElement>();
  62
  63         /**
  64          * Tells whether the template contains elements.
  65          */
  66         public boolean isEmpty() {
  67                 return elements.isEmpty();
  68         }
  69
  70         /**
  71          * The first endpoint (in sequence order) of the template.
  72          * If there are multiple connected components, the first elements of one
  73          * connected component will be returned.
  74          * If the template contains no elements, null is returned.
  75          * If there is a cycle, an arbitrary endpoint will be returned
  76          * (as it then does not make sense to define the first endpoint).
  77          * Time: O(n)
  78          */
  79         public RNATemplateElement getFirst() {
  80                 return getFirstEndPoint().getElement();
  81         }
  82
  83         /**
  84          * The first endpoint edge endpoint (in sequence order) of the template.
  85          * If there are multiple connected components, the first elements of one
  86          * connected component will be returned.
  87          * If the template contains no elements, null is returned.
  88          * If there is a cycle, an arbitrary endpoint will be returned
  89          * (as it then does not make sense to define the first endpoint).
  90          * Time: O(n)
  91          */
  92         public EdgeEndPoint getFirstEndPoint() {
  93                 if (elements.isEmpty()) {
  94                         return null;
  95                 } else {
  96                         Set<EdgeEndPoint> knownEndPoints = new HashSet<EdgeEndPoint>();
  97                         EdgeEndPoint currentEndPoint = getAnyEndPoint();
  98                         while (true) {
  99                                 if (knownEndPoints.contains(currentEndPoint)) {
 100                                         // There is a cycle in the template, so we stop there
 101                                         // to avoid looping infinitely.
 102                                         return currentEndPoint;
 103                                 }
 104                                 knownEndPoints.add(currentEndPoint);
 105                                 EdgeEndPoint previousEndPoint = currentEndPoint.getPreviousEndPoint();
 106                                 if (previousEndPoint == null) {
 107                                         return currentEndPoint;
 108                                 } else {
 109                                         currentEndPoint = previousEndPoint;
 110                                 }
 111                         }
 112                 }
 113         }
 114
 115         /**
 116          * Return an arbitrary element of the template,
 117          * null if empty.
 118          * Time: O(1)
 119          */
 120         public RNATemplateElement getAny() {
 121                 if (elements.isEmpty()) {
 122                         return null;
 123                 } else {
 124                         return elements.iterator().next();
 125                 }
 126         }
 127
 128         /**
 129          * Return an arbitrary endpoint of the template,
 130          * null if empty.
 131          * Time: O(1)
 132          */
 133         public EdgeEndPoint getAnyEndPoint() {
 134                 if (isEmpty()) {
 135                         return null;
 136                 } else {
 137                         return getAny().getIn1EndPoint();
 138                 }
 139         }
 140
 141         /**
 142          * Variable containing "this", used by the internal class
 143          * to access this object.
 144          */
 145         private final RNATemplate template = this;
 146
 147
 148         /**
 149          * To get an iterator of this class, use rnaIterator().
 150          * See rnaIterator() for documentation.
 151          */
 152         private class RNAIterator implements Iterator<RNATemplateElement> {
 153                 private Iterator<EdgeEndPoint> iter = vertexIterator();
 154
 155                 public boolean hasNext() {
 156                         return iter.hasNext();
 157                 }
 158
 159                 public RNATemplateElement next() {
 160                         if (! hasNext()) {
 161                                 throw (new NoSuchElementException());
 162                         }
 163
 164                         EdgeEndPoint currentEndPoint = iter.next();
 165                         switch (currentEndPoint.getPosition()) {
 166                         // We skip "IN" endpoints, so that we don't return elements twice
 167                         case IN1:
 168                         case IN2:
 169                                 // We get the corresponding "OUT" endpoint
 170                                 currentEndPoint = iter.next();
 171                                 break;
 172                         }
 173
 174                         return currentEndPoint.getElement();
 175                 }
 176
 177                 public void remove() {
 178                         throw (new UnsupportedOperationException());
 179                 }
 180
 181         }
 182
 183         /**
 184          * Iterates over the elements of the template, in the sequence order.
 185          * Helixes will be given twice.
 186          * Only one connected component will be iterated on.
 187          * Note that if there is a cycle, the iterator may return a infinite
 188          * number of elements.
 189          */
 190         public Iterator<RNATemplateElement> rnaIterator() {
 191                 return new RNAIterator();
 192         }
 193
 194         /**
 195          * Iterates over all elements (each endpoint is given only once)
 196          * in an arbitrary order.
 197          */
 198         public Iterator<RNATemplateElement> classicIterator() {
 199                 return elements.iterator();
 200         }
 201
 202         private class VertexIterator implements Iterator<EdgeEndPoint> {
 203                 private EdgeEndPoint endpoint = getFirstEndPoint();
 204
 205                 public boolean hasNext() {
 206                         return (endpoint != null);
 207                 }
 208
 209                 public EdgeEndPoint next() {
 210                         if (endpoint == null) {
 211                                 throw (new NoSuchElementException());
 212                         }
 213
 214                         EdgeEndPoint currentEndPoint = endpoint;
 215                         endpoint = currentEndPoint.getNextEndPoint();
 216                         return currentEndPoint;
 217                 }
 218
 219                 public void remove() {
 220                         throw (new UnsupportedOperationException());
 221                 }
 222         }
 223
 224         /**
 225          * Iterates over the elements edge endpoints of the template,
 226          * in the sequence order.
 227          * Only one connected component will be iterated on.
 228          * Note that if there is a cycle, the iterator may return a infinite
 229          * number of elements.
 230          */
 231         public Iterator<EdgeEndPoint> vertexIterator() {
 232                 return new VertexIterator();
 233         }
 234
 235
 236
 237         private class MakeEdgeList {
 238                 List<EdgeEndPoint> list = new LinkedList<EdgeEndPoint>();
 239
 240                 private void addEdgeIfNecessary(EdgeEndPoint endPoint) {
 241                         if (endPoint.isConnected()) {
 242                                 list.add(endPoint);
 243                         }
 244                 }
 245
 246                 public List<EdgeEndPoint> make() {
 247                         for (RNATemplateElement element: elements) {
 248                                 if (element instanceof RNATemplateHelix) {
 249                                         RNATemplateHelix helix = (RNATemplateHelix) element;
 250                                         addEdgeIfNecessary(helix.getIn1());
 251                                         addEdgeIfNecessary(helix.getIn2());
 252                                 } else if (element instanceof RNATemplateUnpairedSequence) {
 253                                         RNATemplateUnpairedSequence sequence = (RNATemplateUnpairedSequence) element;
 254                                         addEdgeIfNecessary(sequence.getIn());
 255                                 }
 256                         }
 257                         return list;
 258                 }
 259         }
 260
 261         /**
 262          * Return over all edges in an arbitrary order.
 263          * For each edge, the first (5' side) endpoint will be given.
 264          */
 265         public List<EdgeEndPoint> makeEdgeList() {
 266                 MakeEdgeList listMaker = new MakeEdgeList();
 267                 return listMaker.make();
 268         }
 269
 270
 271
 272
 273
 274         private class RemovePseudoKnots {
 275                 /**
 276                  * The elements of the template as an array, in the order of the
 277                  * RNA sequence. Note that helixes will appear twice,
 278                  * and non-paired sequences don't appear.
 279                  */
 280                 private ArrayList<RNATemplateHelix> helixesSeq;
 281
 282                 /**
 283                  * For any i,
 284                  * j = helixesStruct[i] is the index in helixesSeq
 285                  * where the same helix also appears.
 286                  * It means we have for all i:
 287                  * helixesSeq[helixesStruct[i]] == helixesSeq[i]
 288                  */
 289                 private ArrayList<Integer> helixesStruct;
 290
 291                 /**
 292                  * The same as helixesStruct, but without the pseudoknots,
 293                  * ie. helixesStructWithoutPseudoKnots[i] may be -1
 294                  * even though helixesStruct[i] != -1 .
 295                  */
 296                 private int[] helixesStructWithoutPseudoKnots;
 297
 298
 299                 private void initArrays() throws ExceptionInvalidRNATemplate {
 300                         helixesSeq = new ArrayList<RNATemplateHelix>();
 301                         helixesStruct = new ArrayList<Integer>();
 302                         Map<RNATemplateHelix,Integer> knownHelixes = new Hashtable<RNATemplateHelix,Integer>();
 303                         Iterator<RNATemplateElement> iter = rnaIterator();
 304                         while (iter.hasNext()) {
 305                                 RNATemplateElement element = iter.next();
 306                                 if (element instanceof RNATemplateHelix) {
 307                                         helixesSeq.add((RNATemplateHelix) element);
 308                                         int index = helixesSeq.size() - 1;
 309                                         if (knownHelixes.containsKey(element)) {
 310                                                 // This is the second time we meet this helix.
 311                                                 int otherOccurenceIndex = knownHelixes.get(element);
 312                                                 helixesStruct.add(otherOccurenceIndex);
 313                                                 if (helixesStruct.get(otherOccurenceIndex) != -1) {
 314                                                         throw (new ExceptionInvalidRNATemplate("We met an helix 3 times. Is there a cycle?"));
 315                                                 }
 316                                                 // Now we know the partner of the other part of
 317                                                 // the helix.
 318                                                 helixesStruct.set(otherOccurenceIndex, index);
 319                                         } else {
 320                                                 // This is the first time we meet this helix.
 321                                                 // Remember its index
 322                                                 knownHelixes.put((RNATemplateHelix) element, index);
 323                                                 // For the moment we don't know where the other part
 324                                                 // of the helix is, but this will be found later.
 325                                                 helixesStruct.add(-1);
 326                                         }
 327                                 }
 328                         }
 329
 330                 }
 331
 332                 /**
 333                  * Tells whether there is a pseudoknot.
 334                  * Adapted from RNAMLParser.isSelfCrossing()
 335                  */
 336                 private boolean isSelfCrossing() {
 337                         Stack<Point> intervals = new Stack<Point>();
 338                         intervals.add(new Point(0, helixesStruct.size() - 1));
 339                         while (!intervals.empty()) {
 340                                 Point p = intervals.pop();
 341                                 if (p.x <= p.y) {
 342                                         if (helixesStruct.get(p.x) == -1) {
 343                                                 intervals.push(new Point(p.x + 1, p.y));
 344                                         } else {
 345                                                 int i = p.x;
 346                                                 int j = p.y;
 347                                                 int k = helixesStruct.get(i);
 348                                                 if ((k <= i) || (k > j)) {
 349                                                         return true;
 350                                                 } else {
 351                                                         intervals.push(new Point(i + 1, k - 1));
 352                                                         intervals.push(new Point(k + 1, j));
 353                                                 }
 354                                         }
 355                                 }
 356                         }
 357                         return false;
 358                 }
 359
 360                 /**
 361                  * We compute helixesStructWithoutPseudoKnots
 362                  * from helixesStruct by replacing values by -1
 363                  * for the helixes we cut (the bases are become non-paired).
 364                  * We try to cut as few base pairs as possible.
 365                  */
 366                 private void removePseudoKnotsAux() {
 367                         if (!isSelfCrossing()) {
 368                                 helixesStructWithoutPseudoKnots = new int[helixesStruct.size()];
 369                                 for (int i=0; i<helixesStructWithoutPseudoKnots.length; i++) {
 370                                         helixesStructWithoutPseudoKnots[i] = helixesStruct.get(i);
 371                                 }
 372                         } else {
 373
 374                                 // We need to get rid of pseudoknots
 375                                 // This code was adapted from RNAMLParser.planarize()
 376                                 int length = helixesStruct.size();
 377
 378                                 int[] result = new int[length];
 379                                 for (int i = 0; i < result.length; i++) {
 380                                         result[i] = -1;
 381                                 }
 382
 383                                 short[][] tab = new short[length][length];
 384                                 short[][] backtrack = new short[length][length];
 385
 386                                 // On the diagonal we have intervals containing only
 387                                 // one endpoint. Therefore there can be no helix
 388                                 // (because an helix consists of 2 elements).
 389                                 for (int i = 0; i < result.length; i++) {
 390                                         // tab[i][j] = 0;
 391                                         backtrack[i][i] = -1;
 392                                 }
 393
 394                                 for (int n = 1; n < length; n++) {
 395                                         for (int i = 0; i < length - n; i++) {
 396                                                 int j = i + n;
 397                                                 tab[i][j] = tab[i + 1][j];
 398                                                 backtrack[i][j] = -1;
 399                                                 int k = helixesStruct.get(i);
 400                                                 assert k != -1;
 401                                                 if ((k <= j) && (i < k)) {
 402                                                         int tmp = helixesSeq.get(i).getLength();
 403                                                         if (i + 1 <= k - 1) {
 404                                                                 tmp += tab[i + 1][k - 1];
 405                                                         }
 406                                                         if (k + 1 <= j) {
 407                                                                 tmp += tab[k + 1][j];
 408                                                         }
 409                                                         if (tmp > tab[i][j]) {
 410                                                                 tab[i][j] = (short) tmp;
 411                                                                 backtrack[i][j] = (short) k;
 412                                                         }
 413                                                 }
 414                                         }
 415                                 }
 416
 417                                 // debug
 418                                 //RNATemplateTests.printShortMatrix(tab);
 419
 420                                 Stack<Point> intervals = new Stack<Point>();
 421                                 intervals.add(new Point(0, length - 1));
 422                                 while (!intervals.empty()) {
 423                                         Point p = intervals.pop();
 424                                         if (p.x <= p.y) {
 425                                                 if (backtrack[p.x][p.y] == -1) {
 426                                                         result[p.x] = -1;
 427                                                         intervals.push(new Point(p.x + 1, p.y));
 428                                                 } else {
 429                                                         int i = p.x;
 430                                                         int j = p.y;
 431                                                         int k = backtrack[i][j];
 432                                                         result[i] = k;
 433                                                         result[k] = i;
 434                                                         intervals.push(new Point(i + 1, k - 1));
 435                                                         intervals.push(new Point(k + 1, j));
 436                                                 }
 437                                         }
 438                                 }
 439
 440                                 helixesStructWithoutPseudoKnots = result;
 441                         }
 442                 }
 443
 444                 private Set<RNATemplateHelix> makeSet() {
 445                         Set<RNATemplateHelix> removedHelixes = new HashSet<RNATemplateHelix>();
 446
 447                         for (int i=0; i<helixesStructWithoutPseudoKnots.length; i++) {
 448                                 if (helixesStructWithoutPseudoKnots[i] < 0) {
 449                                         removedHelixes.add(helixesSeq.get(i));
 450                                 }
 451                         }
 452
 453                         return removedHelixes;
 454                 }
 455
 456                 public Set<RNATemplateHelix> removePseudoKnots() throws ExceptionInvalidRNATemplate {
 457                         initArrays();
 458
 459                         removePseudoKnotsAux();
 460                         // debug
 461                         //printIntArrayList(helixesStruct);
 462                         //printIntArray(helixesStructWithoutPseudoKnots);
 463
 464                         return makeSet();
 465                 }
 466         }
 467
 468         private class ConvertToTree {
 469                 private Set<RNATemplateHelix> removedHelixes;
 470
 471                 public ConvertToTree(Set<RNATemplateHelix> removedHelixes) {
 472                         this.removedHelixes = removedHelixes;
 473                 }
 474
 475                 private Iterator<RNATemplateElement> iter = template.rnaIterator();
 476                 private Set<RNATemplateHelix> knownHelixes = new HashSet<RNATemplateHelix>();
 477
 478                 public Tree<RNANodeValueTemplate> convert() throws ExceptionInvalidRNATemplate {
 479                         Tree<RNANodeValueTemplate> root = new Tree<RNANodeValueTemplate>();
 480                          // No value, this is a fake node because we need a root.
 481                         root.setValue(null);
 482                         makeChildren(root);
 483                         return root;
 484                 }
 485
 486                 private void makeChildren(Tree<RNANodeValueTemplate> father) throws ExceptionInvalidRNATemplate {
 487                         List<Tree<RNANodeValueTemplate>> children = father.getChildren();
 488                         while (true) {
 489                                 try {
 490                                         RNATemplateElement element = iter.next();
 491                                         if (element instanceof RNATemplateHelix) {
 492                                                 RNATemplateHelix helix = (RNATemplateHelix) element;
 493                                                 if (removedHelixes.contains(helix)) {
 494                                                         // Helix was removed
 495
 496                                                         boolean firstPartOfHelix;
 497                                                         if (knownHelixes.contains(helix)) {
 498                                                                 firstPartOfHelix = false;
 499                                                         } else {
 500                                                                 knownHelixes.add(helix);
 501                                                                 firstPartOfHelix = true;
 502                                                         }
 503
 504                                                         int helixLength = helix.getLength();
 505                                                         // Maybe we could allow helixes of length 0?
 506                                                         // If we want to then this code can be changed in the future.
 507                                                         if (helixLength < 1) {
 508                                                                 throw (new ExceptionInvalidRNATemplate("Helix length < 1"));
 509                                                         }
 510                                                         int firstPosition = firstPartOfHelix ? 0 : helixLength;
 511                                                         int afterLastPosition = firstPartOfHelix ? helixLength : 2*helixLength;
 512                                                         for (int i=firstPosition; i<afterLastPosition; i++) {
 513                                                                 RNANodeValueTemplateBrokenBasePair value = new RNANodeValueTemplateBrokenBasePair();
 514                                                                 value.setHelix(helix);
 515                                                                 value.setPositionInHelix(i);
 516                                                                 Tree<RNANodeValueTemplate> child = new Tree<RNANodeValueTemplate>();
 517                                                                 child.setValue(value);
 518                                                                 father.getChildren().add(child);
 519                                                         }
 520
 521                                                 } else {
 522                                                         // We have an non-removed helix
 523
 524                                                         if (knownHelixes.contains(helix)) {
 525                                                                 if ((! (father.getValue() instanceof RNANodeValueTemplateBasePair))
 526                                                                                 || ((RNANodeValueTemplateBasePair) father.getValue()).getHelix() != helix) {
 527                                                                         // We have already met this helix, so unless it is our father,
 528                                                                         // we have a pseudoknot (didn't we remove them???).
 529                                                                         throw (new ExceptionInvalidRNATemplate("Unexpected helix. Looks like there still are pseudoknots even after we removed them so something is wrong about the template."));
 530                                                                 } else {
 531                                                                         // As we have found the father, we have finished our work
 532                                                                         // with the children.
 533                                                                         return;
 534                                                                 }
 535                                                         } else {
 536                                                                 knownHelixes.add(helix);
 537
 538                                                                 int helixLength = helix.getLength();
 539                                                                 // Maybe we could allow helixes of length 0?
 540                                                                 // If we want to then this code can be changed in the future.
 541                                                                 if (helixLength < 1) {
 542                                                                         throw (new ExceptionInvalidRNATemplate("Helix length < 1"));
 543                                                                 }
 544                                                                 Tree<RNANodeValueTemplate> lastChild = father;
 545                                                                 for (int i=0; i<helixLength; i++) {
 546                                                                         RNANodeValueTemplateBasePair value = new RNANodeValueTemplateBasePair();
 547                                                                         value.setHelix(helix);
 548                                                                         value.setPositionInHelix(i);
 549                                                                         Tree<RNANodeValueTemplate> child = new Tree<RNANodeValueTemplate>();
 550                                                                         child.setValue(value);
 551                                                                         lastChild.getChildren().add(child);
 552                                                                         lastChild = child;
 553                                                                 }
 554                                                                 // Now we put what follows as children of lastChild
 555                                                                 makeChildren(lastChild);
 556                                                         }
 557
 558
 559                                                 }
 560                                         } else if (element instanceof RNATemplateUnpairedSequence) {
 561                                                 RNATemplateUnpairedSequence sequence = (RNATemplateUnpairedSequence) element;
 562                                                 int seqLength = sequence.getLength();
 563
 564                                                 // Maybe we could allow sequences of length 0?
 565                                                 // If we want to then this code can be changed in the future.
 566                                                 if (seqLength < 1) {
 567                                                         throw (new ExceptionInvalidRNATemplate("Non-paired sequence length < 1"));
 568                                                 }
 569
 570                                                 RNANodeValueTemplateSequence value = new RNANodeValueTemplateSequence();
 571                                                 value.setSequence(sequence);
 572                                                 Tree<RNANodeValueTemplate> child = new Tree<RNANodeValueTemplate>();
 573                                                 child.setValue(value);
 574                                                 children.add(child);
 575                                         } else {
 576                                                 throw (new ExceptionInvalidRNATemplate("We have an endpoint which is neither an helix nor a sequence. What is that?"));
 577                                         }
 578
 579                                 } catch (NoSuchElementException e) {
 580                                         // We are at the end of elements so if everything is ok
 581                                         // the father must be the root.
 582                                         if (father.getValue() == null) {
 583                                                 return; // Work finished.
 584                                         } else {
 585                                                 throw (new ExceptionInvalidRNATemplate("Unexpected end of template endpoint list."));
 586                                         }
 587                                 }
 588                         }
 589                 }
 590
 591         }
 592
 593         /**
 594          * Tells whether the connected component to which endPoint belongs to
 595          * is cyclic.
 596          */
 597         public boolean connectedComponentIsCyclic(EdgeEndPoint endPoint) {
 598                 Set<EdgeEndPoint> knownEndPoints = new HashSet<EdgeEndPoint>();
 599                 EdgeEndPoint currentEndPoint = endPoint;
 600                 while (true) {
 601                         if (knownEndPoints.contains(currentEndPoint)) {
 602                                 return true;
 603                         }
 604                         knownEndPoints.add(currentEndPoint);
 605                         EdgeEndPoint previousEndPoint = currentEndPoint.getPreviousEndPoint();
 606                         if (previousEndPoint == null) {
 607                                 return false;
 608                         } else {
 609                                 currentEndPoint = previousEndPoint;
 610                         }
 611                 }
 612         }
 613
 614         /**
 615          * Tells whether the template elements are all connected, ie. if the
 616          * graph (edge endpoints being vertices) is connected.
 617          */
 618         public boolean isConnected() {
 619                 if (isEmpty()) {
 620                         return true;
 621                 }
 622
 623                 // Count all vertices
 624                 int n = 0;
 625                 for (RNATemplateElement element: elements) {
 626                         if (element instanceof RNATemplateHelix) {
 627                                 n += 4;
 628                         } else if (element instanceof RNATemplateUnpairedSequence) {
 629                                 n += 2;
 630                         }
 631                 }
 632
 633                 // Now try reaching all vertices
 634                 Set<EdgeEndPoint> knownEndPoints = new HashSet<EdgeEndPoint>();
 635                 EdgeEndPoint currentEndPoint = getFirstEndPoint();
 636                 while (true) {
 637                         if (knownEndPoints.contains(currentEndPoint)) {
 638                                 // We are back to our original endpoint, so stop
 639                                 break;
 640                         }
 641                         knownEndPoints.add(currentEndPoint);
 642                         EdgeEndPoint nextEndPoint = currentEndPoint.getNextEndPoint();
 643                         if (nextEndPoint == null) {
 644                                 break;
 645                         } else {
 646                                 currentEndPoint = nextEndPoint;
 647                         }
 648                 }
 649
 650                 // The graph is connected iff the number of reached vertices
 651                 // is equal to the total number of vertices.
 652                 return (knownEndPoints.size() == n);
 653
 654         }
 655
 656         /**
 657          * Checks whether this template is a valid RNA template, ie.
 658          * it is non-empty, it does not contain a cycle and all elements are in one
 659          * connected component.
 660          */
 661         public void checkIsValidTemplate() throws ExceptionInvalidRNATemplate {
 662                 if (isEmpty()) {
 663                         throw (new ExceptionInvalidRNATemplate("The template is empty."));
 664                 }
 665
 666                 if (! isConnected()) {
 667                         throw (new ExceptionInvalidRNATemplate("The template is a non-connected graph."));
 668                 }
 669
 670                 // Now we know the graph is connected.
 671
 672                 if (connectedComponentIsCyclic(getAnyEndPoint())) {
 673                         throw (new ExceptionInvalidRNATemplate("The template is cyclic."));
 674                 }
 675         }
 676
 677         /**
 678          * Make a tree of the template. For this, we will remove pseudoknots,
 679          * taking care to remove as few base pair links as possible.
 680          * Requires the template to be valid and will check the validity
 681          * (will call checkIsValidTemplate()).
 682          * Calling this method will automatically call computeIn1Is().
 683          */
 684         public Tree<RNANodeValueTemplate> toTree() throws ExceptionInvalidRNATemplate {
 685                 // Compute the helix in1Is fields.
 686                 // We also rely on computeIn1Is() for checking the template validity.
 687                 computeIn1Is();
 688
 689                 // Remove pseudoknots
 690                 RemovePseudoKnots pseudoKnotKiller = new RemovePseudoKnots();
 691                 Set<RNATemplateHelix> removedHelixes = pseudoKnotKiller.removePseudoKnots();
 692
 693                 // Convert to tree
 694                 ConvertToTree converter = new ConvertToTree(removedHelixes);
 695                 return converter.convert();
 696         }
 697
 698
 699         /**
 700          * Generate an RNA sequence that exactly matches the template.
 701          * Requires the template to be valid and will check the validity
 702          * (will call checkIsValidTemplate()).
 703          */
 704         public RNA toRNA() throws ExceptionInvalidRNATemplate {
 705                 // First, we check this is a valid template
 706                 checkIsValidTemplate();
 707
 708                 ArrayList<Integer> str = new ArrayList<Integer>();
 709                 Map<RNATemplateHelix, ArrayList<Integer>> helixes = new HashMap<RNATemplateHelix, ArrayList<Integer>>();
 710                 Iterator<RNATemplateElement> iter = rnaIterator();
 711                 while (iter.hasNext()) {
 712                         RNATemplateElement element = iter.next();
 713                         if (element instanceof RNATemplateHelix) {
 714                                 RNATemplateHelix helix = (RNATemplateHelix) element;
 715                                 int n = helix.getLength();
 716                                 if (helixes.containsKey(helix)) {
 717                                         int firstBase = str.size();
 718                                         ArrayList<Integer> helixMembers = helixes.get(helix);
 719                                         for (int i = 0; i < n; i++) {
 720                                                 int indexOfAssociatedBase = helixMembers.get(n-1-i);
 721                                                 str.set(indexOfAssociatedBase, firstBase + i);
 722                                                 str.add(indexOfAssociatedBase);
 723                                         }
 724                                 } else {
 725                                         int firstBase = str.size();
 726                                         ArrayList<Integer> helixMembers = new ArrayList<Integer>();
 727                                         for (int i = 0; i < n; i++) {
 728                                                 // We don't known yet where the associated base is
 729                                                 str.add(-1);
 730                                                 helixMembers.add(firstBase + i);
 731                                         }
 732                                         helixes.put(helix, helixMembers);
 733                                 }
 734                         } else if (element instanceof RNATemplateUnpairedSequence) {
 735                                 RNATemplateUnpairedSequence sequence = (RNATemplateUnpairedSequence) element;
 736                                 int n = sequence.getLength();
 737                                 for (int i=0; i<n; i++) {
 738                                         str.add(-1);
 739                                 }
 740                         } else {
 741                                 throw (new ExceptionInvalidRNATemplate("We have an endpoint which is neither an helix nor a sequence. What is that?"));
 742                         }
 743                 }
 744
 745                 int[] strAsArray = RNATemplateAlign.intArrayFromList(str);
 746                 String[] seqAsArray = new String[strAsArray.length];
 747                 Arrays.fill(seqAsArray, " ");
 748                 RNA rna = new RNA();
 749                 try {
 750                         rna.setRNA(seqAsArray, strAsArray);
 751                 } catch (ExceptionFileFormatOrSyntax e) {
 752                         throw (new RuntimeException("Bug in toRNA(): setRNA() threw an ExceptionFileFormatOrSyntax exception."));
 753                 }
 754                 return rna;
 755         }
 756
 757
 758         private class ConvertToXml {
 759                 private Map<RNATemplateElement, String> elementNames = new HashMap<RNATemplateElement, String>();
 760                 private Element connectionsXmlElement;
 761                 private Document document;
 762
 763                 private void addConnectionIfNecessary(EdgeEndPoint endPoint) {
 764                         if (endPoint != null && endPoint.isConnected()) {
 765                                 RNATemplateElement e1 = endPoint.getElement();
 766                                 EdgeEndPointPosition p1 = endPoint.getPosition();
 767                                 RNATemplateElement e2 = endPoint.getOtherElement();
 768                                 EdgeEndPointPosition p2 = endPoint.getOtherEndPoint().getPosition();
 769                                 Element xmlElement = document.createElement("edge");
 770                                 {
 771                                         Element fromXmlElement = document.createElement("from");
 772                                         fromXmlElement.setAttribute("endpoint", elementNames.get(e1));
 773                                         fromXmlElement.setAttribute("position", p1.toString());
 774                                         xmlElement.appendChild(fromXmlElement);
 775                                 }
 776                                 {
 777                                         Element toXmlElement = document.createElement("to");
 778                                         toXmlElement.setAttribute("endpoint", elementNames.get(e2));
 779                                         toXmlElement.setAttribute("position", p2.toString());
 780                                         xmlElement.appendChild(toXmlElement);
 781                                 }
 782                                 connectionsXmlElement.appendChild(xmlElement);
 783                         }
 784                 }
 785
 786                 public Document toXMLDocument() throws ExceptionXMLGeneration, ExceptionInvalidRNATemplate {
 787                         try {
 788                                 DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
 789                                 DocumentBuilder builder = factory.newDocumentBuilder();
 790                                 document = builder.newDocument();
 791                                 Element root = document.createElement("RNATemplate");
 792                                 document.appendChild(root);
 793                                 Element elementsXmlElement = document.createElement("elements");
 794                                 root.appendChild(elementsXmlElement);
 795                                 connectionsXmlElement = document.createElement("edges");
 796                                 root.appendChild(connectionsXmlElement);
 797
 798                                 // First pass, we create a mapping between java references and names (strings)
 799                                 {
 800                                         int nextHelix = 1;
 801                                         int nextNonPairedSequence = 1;
 802                                         for (RNATemplateElement templateElement: elements) {
 803                                                 if (templateElement instanceof RNATemplateHelix) {
 804                                                         RNATemplateHelix helix = (RNATemplateHelix) templateElement;
 805                                                         if (! elementNames.containsKey(helix)) {
 806                                                                 elementNames.put(helix, "H ID " + nextHelix);
 807                                                                 nextHelix++;
 808                                                         }
 809                                                 } else if (templateElement instanceof RNATemplateUnpairedSequence) {
 810                                                         RNATemplateUnpairedSequence sequence = (RNATemplateUnpairedSequence) templateElement;
 811                                                         if (! elementNames.containsKey(sequence)) {
 812                                                                 elementNames.put(sequence, "S ID " + nextNonPairedSequence);
 813                                                                 nextNonPairedSequence++;
 814                                                         }
 815                                                 } else {
 816                                                         throw (new ExceptionInvalidRNATemplate("We have an endpoint which is neither an helix nor a sequence. What is that?"));
 817                                                 }
 818                                         }
 819                                 }
 820
 821                                 // Now we generate the XML document
 822                                 for (RNATemplateElement templateElement: elements) {
 823                                         String elementXmlName = elementNames.get(templateElement);
 824                                         Element xmlElement;
 825                                         if (templateElement instanceof RNATemplateHelix) {
 826                                                 RNATemplateHelix helix = (RNATemplateHelix) templateElement;
 827                                                 xmlElement = document.createElement("helix");
 828                                                 xmlElement.setAttribute("id", elementXmlName);
 829                                                 xmlElement.setAttribute("length", Integer.toString(helix.getLength()));
 830                                                 xmlElement.setAttribute("flipped", Boolean.toString(helix.isFlipped()));
 831                                                 if (helix.hasCaption()) {
 832                                                         xmlElement.setAttribute("caption", helix.getCaption());
 833                                                 }
 834                                                 {
 835                                                         Element startPositionXmlElement = document.createElement("startPosition");
 836                                                         startPositionXmlElement.setAttribute("x", Double.toString(helix.getStartPosition().x));
 837                                                         startPositionXmlElement.setAttribute("y", Double.toString(helix.getStartPosition().y));
 838                                                         xmlElement.appendChild(startPositionXmlElement);
 839                                                 }
 840                                                 {
 841                                                         Element endPositionXmlElement = document.createElement("endPosition");
 842                                                         endPositionXmlElement.setAttribute("x", Double.toString(helix.getEndPosition().x));
 843                                                         endPositionXmlElement.setAttribute("y", Double.toString(helix.getEndPosition().y));
 844                                                         xmlElement.appendChild(endPositionXmlElement);
 845                                                 }
 846                                                 addConnectionIfNecessary(helix.getOut1());
 847                                                 addConnectionIfNecessary(helix.getOut2());
 848                                         } else if (templateElement instanceof RNATemplateUnpairedSequence) {
 849                                                 RNATemplateUnpairedSequence sequence = (RNATemplateUnpairedSequence) templateElement;
 850                                                 xmlElement = document.createElement("sequence");
 851                                                 xmlElement.setAttribute("id", elementXmlName);
 852                                                 xmlElement.setAttribute("length", Integer.toString(sequence.getLength()));
 853                                                 {
 854                                                         Element vertex5XmlElement = document.createElement("vertex5");
 855                                                         vertex5XmlElement.setAttribute("x", Double.toString(sequence.getVertex5().x));
 856                                                         vertex5XmlElement.setAttribute("y", Double.toString(sequence.getVertex5().y));
 857                                                         xmlElement.appendChild(vertex5XmlElement);
 858                                                 }
 859                                                 {
 860                                                         Element vertex3XmlElement = document.createElement("vertex3");
 861                                                         vertex3XmlElement.setAttribute("x", Double.toString(sequence.getVertex3().x));
 862                                                         vertex3XmlElement.setAttribute("y", Double.toString(sequence.getVertex3().y));
 863                                                         xmlElement.appendChild(vertex3XmlElement);
 864                                                 }
 865                                                 {
 866                                                         Element inTangentVectorXmlElement = document.createElement("inTangentVector");
 867                                                         inTangentVectorXmlElement.setAttribute("angle", Double.toString(sequence.getInTangentVectorAngle()));
 868                                                         inTangentVectorXmlElement.setAttribute("length", Double.toString(sequence.getInTangentVectorLength()));
 869                                                         xmlElement.appendChild(inTangentVectorXmlElement);
 870                                                 }
 871                                                 {
 872                                                         Element outTangentVectorXmlElement = document.createElement("outTangentVector");
 873                                                         outTangentVectorXmlElement.setAttribute("angle", Double.toString(sequence.getOutTangentVectorAngle()));
 874                                                         outTangentVectorXmlElement.setAttribute("length", Double.toString(sequence.getOutTangentVectorLength()));
 875                                                         xmlElement.appendChild(outTangentVectorXmlElement);
 876                                                 }
 877                                                 addConnectionIfNecessary(sequence.getOut());
 878                                         } else {
 879                                                 throw (new ExceptionInvalidRNATemplate("We have an endpoint which is neither an helix nor a sequence. What is that?"));
 880                                         }
 881                                         elementsXmlElement.appendChild(xmlElement);
 882                                 }
 883
 884                                 return document;
 885                         } catch (ParserConfigurationException e) {
 886                                 throw (new ExceptionXMLGeneration("ParserConfigurationException: " + e.getMessage()));
 887                         }
 888                 }
 889         }
 890
 891
 892
 893         public void toXMLFile(File file) throws ExceptionXMLGeneration, ExceptionInvalidRNATemplate {
 894                 try {
 895                         Document xmlDocument = toXMLDocument();
 896                         Source source = new DOMSource(xmlDocument);
 897                         Result result = new StreamResult(file);
 898                         Transformer transformer;
 899                         transformer = TransformerFactory.newInstance().newTransformer();
 900                         transformer.setOutputProperty(OutputKeys.INDENT, "yes");
 901                         transformer.transform(source, result);
 902                 } catch (TransformerConfigurationException e) {
 903                         throw (new ExceptionXMLGeneration("TransformerConfigurationException: " + e.getMessage()));
 904                 } catch (TransformerFactoryConfigurationError e) {
 905                         throw (new ExceptionXMLGeneration("TransformerFactoryConfigurationError: " + e.getMessage()));
 906                 } catch (TransformerException e) {
 907                         throw (new ExceptionXMLGeneration("TransformerException: " + e.getMessage()));
 908                 }
 909         }
 910
 911
 912         public Document toXMLDocument() throws ExceptionXMLGeneration, ExceptionInvalidRNATemplate {
 913                 ConvertToXml converter = new ConvertToXml();
 914                 return converter.toXMLDocument();
 915         }
 916
 917
 918         private class LoadFromXml {
 919                 private Document xmlDocument;
 920                 private Map<String, RNATemplateElement> elementNames = new HashMap<String, RNATemplateElement>();
 921
 922                 public LoadFromXml(Document xmlDocument) {
 923                         this.xmlDocument = xmlDocument;
 924                 }
 925
 926                 private Point2D.Double pointFromXml(Element xmlPoint) {
 927                         Point2D.Double point = new Point2D.Double();
 928                         point.x = Double.parseDouble(xmlPoint.getAttribute("x"));
 929                         point.y = Double.parseDouble(xmlPoint.getAttribute("y"));
 930                         return point;
 931                 }
 932
 933                 private double vectorLengthFromXml(Element xmlVector) {
 934                         return Double.parseDouble(xmlVector.getAttribute("length"));
 935                 }
 936
 937                 private double vectorAngleFromXml(Element xmlVector) {
 938                         return Double.parseDouble(xmlVector.getAttribute("angle"));
 939                 }
 940
 941                 /**
 942                  * Takes an element of the form:
 943                  * <anything endpoint="an element id" position="a valid EdgeEndPointPosition"/>
 944                  * and returns the corresponding EdgeEndPoint object.
 945                  */
 946                 private EdgeEndPoint endPointFromXml(Element xmlEdgeEndPoint) throws ExceptionXmlLoading {
 947                         String elementId = xmlEdgeEndPoint.getAttribute("endpoint");
 948                         if (elementId == null || elementId == "")
 949                                 throw (new ExceptionXmlLoading ("Missing endpoint attribute on " + xmlEdgeEndPoint));
 950                         String positionOnElement = xmlEdgeEndPoint.getAttribute("position");
 951                         if (positionOnElement == null || positionOnElement == "")
 952                                 throw (new ExceptionXmlLoading ("Missing position attribute on " + xmlEdgeEndPoint));
 953                         if (elementNames.containsKey(elementId)) {
 954                                 RNATemplateElement templateElement = elementNames.get(elementId);
 955                                 EdgeEndPointPosition relativePosition = EdgeEndPointPosition.valueOf(positionOnElement);
 956                                 if (relativePosition == null)
 957                                         throw (new ExceptionXmlLoading ("Could not compute relativePosition"));
 958                                 return templateElement.getEndPointFromPosition(relativePosition);
 959                         } else {
 960                                 throw (new ExceptionXmlLoading("Edge is connected on unkown element: " + elementId));
 961                         }
 962                 }
 963
 964                 private String connectErrMsg(EdgeEndPoint v1, EdgeEndPoint v2, String reason) {
 965                         return "Error while connecting\n"
 966                         + v1.toString() + " to\n"
 967                         + v2.toString() + " because:\n"
 968                         + reason;
 969                 }
 970
 971                 private void connect(EdgeEndPoint v1, EdgeEndPoint v2) throws ExceptionXmlLoading {
 972                         if (v1 == null || v2 == null) {
 973                                 throw (new ExceptionXmlLoading("Invalid edge: missing endpoint\n v1 = " + v1 + "\n v2 = " + v2));
 974                         }
 975                         if (v2.isConnected()) {
 976                                 throw (new ExceptionXmlLoading(connectErrMsg(v1, v2, "Second vertex is already connected to " + v2.getOtherElement().toString())));
 977                         }
 978                         if (v1.isConnected()) {
 979                                 throw (new ExceptionXmlLoading(connectErrMsg(v1, v2, "First vertex is already connected to " + v1.getOtherElement().toString())));
 980                         }
 981
 982                         try {
 983                                 v1.connectTo(v2);
 984                         } catch (ExceptionEdgeEndpointAlreadyConnected e) {
 985                                 throw (new ExceptionXmlLoading("A vertex is on two edges at the same time: " + e.getMessage()));
 986                         } catch (ExceptionInvalidRNATemplate e) {
 987                                 throw (new ExceptionXmlLoading("ExceptionInvalidRNATemplate: " + e.getMessage()));
 988                         }
 989                 }
 990
 991                 public void load() throws ExceptionXmlLoading {
 992                         // First part: we load all elements from the XML tree
 993                         Element xmlElements = (Element) xmlDocument.getElementsByTagName("elements").item(0);
 994                         {
 995                                 NodeList xmlElementsChildren = xmlElements.getChildNodes();
 996                                 for (int i=0; i<xmlElementsChildren.getLength(); i++) {
 997                                         Node xmlElementsChild = xmlElementsChildren.item(i);
 998                                         if (xmlElementsChild instanceof Element) {
 999                                                 Element xmlTemplateElement = (Element) xmlElementsChild;
1000                                                 String tagName = xmlTemplateElement.getTagName();
1001                                                 if (tagName == "helix") {
1002                                                         RNATemplateHelix helix = new RNATemplateHelix(xmlTemplateElement.getAttribute("id"));
1003                                                         helix.setFlipped(Boolean.parseBoolean(xmlTemplateElement.getAttribute("flipped")));
1004                                                         helix.setLength(Integer.parseInt(xmlTemplateElement.getAttribute("length")));
1005                                                         if (xmlTemplateElement.hasAttribute("caption")) {
1006                                                                 helix.setCaption(xmlTemplateElement.getAttribute("caption"));
1007                                                         }
1008                                                         elementNames.put(xmlTemplateElement.getAttribute("id"), helix);
1009                                                         NodeList xmlHelixChildren = xmlTemplateElement.getChildNodes();
1010                                                         for (int j=0; j<xmlHelixChildren.getLength(); j++) {
1011                                                                 Node xmlHelixChild = xmlHelixChildren.item(j);
1012                                                                 if (xmlHelixChild instanceof Element) {
1013                                                                         Element xmlHelixChildElement = (Element) xmlHelixChild;
1014                                                                         String helixChildTagName = xmlHelixChildElement.getTagName();
1015                                                                         if (helixChildTagName == "startPosition") {
1016                                                                                 helix.setStartPosition(pointFromXml(xmlHelixChildElement));
1017                                                                         } else if (helixChildTagName == "endPosition") {
1018                                                                                 helix.setEndPosition(pointFromXml(xmlHelixChildElement));
1019                                                                         }
1020                                                                 }
1021                                                         }
1022                                                 } else if (tagName == "sequence") {
1023                                                         RNATemplateUnpairedSequence sequence = new RNATemplateUnpairedSequence(xmlTemplateElement.getAttribute("id"));
1024                                                         sequence.setLength(Integer.parseInt(xmlTemplateElement.getAttribute("length")));
1025                                                         elementNames.put(xmlTemplateElement.getAttribute("id"), sequence);
1026                                                         NodeList xmlSequenceChildren = xmlTemplateElement.getChildNodes();
1027                                                         for (int j=0; j<xmlSequenceChildren.getLength(); j++) {
1028                                                                 Node xmlSequenceChild = xmlSequenceChildren.item(j);
1029                                                                 if (xmlSequenceChild instanceof Element) {
1030                                                                         Element xmlSequenceChildElement = (Element) xmlSequenceChild;
1031                                                                         String sequenceChildTagName = xmlSequenceChildElement.getTagName();
1032                                                                         if (sequenceChildTagName == "inTangentVector") {
1033                                                                                 sequence.setInTangentVectorLength(vectorLengthFromXml(xmlSequenceChildElement));
1034                                                                                 sequence.setInTangentVectorAngle(vectorAngleFromXml(xmlSequenceChildElement));
1035                                                                         } else if (sequenceChildTagName == "outTangentVector") {
1036                                                                                 sequence.setOutTangentVectorLength(vectorLengthFromXml(xmlSequenceChildElement));
1037                                                                                 sequence.setOutTangentVectorAngle(vectorAngleFromXml(xmlSequenceChildElement));
1038                                                                         } else if (sequenceChildTagName == "vertex5") {
1039                                                                                 sequence.setVertex5(pointFromXml(xmlSequenceChildElement));
1040                                                                         } else if (sequenceChildTagName == "vertex3") {
1041                                                                                 sequence.setVertex3(pointFromXml(xmlSequenceChildElement));
1042                                                                         }
1043                                                                 }
1044                                                         }
1045                                                 }
1046                                         }
1047                                 }
1048                         }
1049
1050                         // Second part: We read the edges from the XML tree
1051                         Element xmlEdges = (Element) xmlDocument.getElementsByTagName("edges").item(0);
1052                         {
1053                                 NodeList xmlEdgesChildren = xmlEdges.getChildNodes();
1054                                 for (int i=0; i<xmlEdgesChildren.getLength(); i++) {
1055                                         Node xmlEdgesChild = xmlEdgesChildren.item(i);
1056                                         if (xmlEdgesChild instanceof Element) {
1057                                                 Element xmlTemplateEdge = (Element) xmlEdgesChild;
1058                                                 if (xmlTemplateEdge.getTagName() == "edge") {
1059                                                         EdgeEndPoint v1 = null, v2 = null;
1060                                                         NodeList xmlEdgeChildren = xmlTemplateEdge.getChildNodes();
1061                                                         for (int j=0; j<xmlEdgeChildren.getLength(); j++) {
1062                                                                 Node xmlEdgeChild = xmlEdgeChildren.item(j);
1063                                                                 if (xmlEdgeChild instanceof Element) {
1064                                                                         Element xmlEdgeChildElement = (Element) xmlEdgeChild;
1065                                                                         String edgeChildTagName = xmlEdgeChildElement.getTagName();
1066                                                                         if (edgeChildTagName == "from") {
1067                                                                                 v1 = endPointFromXml(xmlEdgeChildElement);
1068                                                                         } else if (edgeChildTagName == "to") {
1069                                                                                 v2 = endPointFromXml(xmlEdgeChildElement);
1070                                                                         }
1071                                                                 }
1072                                                         }
1073                                                         if (v1 == null)
1074                                                                 throw (new ExceptionXmlLoading("Invalid edge: missing \"from\" declaration"));
1075                                                         if (v2 == null)
1076                                                                 throw (new ExceptionXmlLoading("Invalid edge: missing \"to\" declaration"));
1077                                                         connect(v1, v2);
1078                                                 }
1079                                         }
1080                                 }
1081
1082                         }
1083                 }
1084         }
1085
1086
1087         public static RNATemplate fromXMLFile(File file) throws ExceptionXmlLoading {
1088                 try {
1089                         DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
1090                         factory.setIgnoringElementContentWhitespace(true);
1091                         DocumentBuilder builder = factory.newDocumentBuilder();
1092                         Document xmlDocument = builder.parse(file);
1093                         return fromXMLDocument(xmlDocument);
1094                 } catch (ParserConfigurationException e) {
1095                         throw (new ExceptionXmlLoading("ParserConfigurationException: " + e.getMessage()));
1096                 } catch (SAXException e) {
1097                         throw (new ExceptionXmlLoading("SAXException: " + e.getMessage()));
1098                 } catch (IOException e) {
1099                         throw (new ExceptionXmlLoading("IOException: " + e.getMessage()));
1100                 }
1101         }
1102
1103
1104         public static RNATemplate fromXMLDocument(Document xmlDocument) throws ExceptionXmlLoading {
1105                 RNATemplate template = new RNATemplate();
1106                 LoadFromXml loader = template.new LoadFromXml(xmlDocument);
1107                 loader.load();
1108                 return template;
1109         }
1110
1111
1112
1113         /**
1114          * For an helix, tells us whether IN1/OUT1 is the 5' strand
1115          * (the first strand we meet if we follow the RNA sequence)
1116          * or the 3' strand (the second we meet if we follow the RNA sequence).
1117          */
1118         public enum In1Is {
1119                 IN1_IS_5PRIME, IN1_IS_3PRIME
1120         }
1121
1122
1123         /**
1124          * For each helix, compute the in1Is field.
1125          * If helices connections are changed, the value may become obsolete,
1126          * so you need to call this method again before accessing the in1Is
1127          * fields if you have modified connections in the template.
1128          * Requires the template to be valid and will check the validity
1129          * (will call checkIsValidTemplate()).
1130          */
1131         public void computeIn1Is() throws ExceptionInvalidRNATemplate {
1132                 checkIsValidTemplate();
1133
1134                 Iterator<EdgeEndPoint> iter = vertexIterator();
1135                 Set<RNATemplateHelix> knownHelices = new HashSet<RNATemplateHelix>();
1136                 while (iter.hasNext()) {
1137                         EdgeEndPoint endPoint = iter.next();
1138                         RNATemplateElement templateElement = endPoint.getElement();
1139                         if (templateElement instanceof RNATemplateHelix) {
1140                                 RNATemplateHelix helix = (RNATemplateHelix) templateElement;
1141                                 if (! knownHelices.contains(helix)) {
1142                                         // first time we meet this helix
1143                                         switch (endPoint.getPosition()) {
1144                                         case IN1:
1145                                         case OUT1:
1146                                                 helix.setIn1Is(In1Is.IN1_IS_5PRIME);
1147                                                 break;
1148                                         case IN2:
1149                                         case OUT2:
1150                                                 helix.setIn1Is(In1Is.IN1_IS_3PRIME);
1151                                                 break;
1152                                         }
1153                                         knownHelices.add(helix);
1154                                 }
1155                         }
1156                 }
1157         }
1158
1159
1160
1161         /**
1162          * Remove the element from the template.
1163          * The element is automatically disconnected from any other element.
1164          * Returns true if and only if the element was present in the template,
1165          * otherwise nothing was done.
1166          */
1167         public boolean removeElement(RNATemplateElement element) throws ExceptionInvalidRNATemplate {
1168                 if (elements.contains(element)) {
1169                         element.disconnectFromAny();
1170                         elements.remove(element);
1171                         return true;
1172                 } else {
1173                         return false;
1174                 }
1175         }
1176
1177
1178         /**
1179          * Position of an endpoint on an endpoint.
1180          * Not all values make sense for any endpoint.
1181          * For an helix, all four make sense, but for a non-paired
1182          * sequence, only IN1 and OUT1 make sense.
1183          */
1184         public enum EdgeEndPointPosition {
1185                 IN1, IN2, OUT1, OUT2;
1186         }
1187
1188
1189         private static int NEXT_ID = 1;
1190
1191         /**
1192          * An endpoint of an RNA template,
1193          * it can be an helix or a sequence of non-paired bases.
1194          *
1195          * You cannot create an object of this class directly,
1196          * use RNATemplateHelix or RNATemplateUnpairedSequence instead.
1197          *
1198          * @author Raphael Champeimont
1199          */
1200         public abstract class RNATemplateElement {
1201
1202                 public int _id = NEXT_ID++;
1203
1204                 public String getName()
1205                 {return "RNATemplate"+_id; }
1206
1207
1208                 /**
1209                  * This variable is just there so that "this" can be accessed by a name
1210                  * from the internal class EdgeEndPoint.
1211                  */
1212                 private final RNATemplateElement element = this;
1213
1214                 /**
1215                  * When the endpoint is created, it is added to the list of elements
1216                  * in this template. To remove it, call RNATemplate.removeElement().
1217                  */
1218                 public RNATemplateElement() {
1219                         elements.add(this);
1220                 }
1221
1222                 /**
1223                  * Disconnect this endpoint from any other elements it may be connected to.
1224                  */
1225                 public abstract void disconnectFromAny();
1226
1227                 /**
1228                  * Get the the IN endpoint in the case of a sequence
1229                  * and the IN1 endpoint in the case of an helix.
1230                  */
1231                 public abstract EdgeEndPoint getIn1EndPoint();
1232
1233                 /**
1234                  * Returns the template to which this endpoint belongs.
1235                  */
1236                 public RNATemplate getParentTemplate() {
1237                         return template;
1238                 }
1239
1240                 /**
1241                  * Provided endpoint is an endpoint of this endpoint, get the next
1242                  * endpoint, either on this same endpoint, or or the connected endpoint.
1243                  * Note that you should use the getNextEndPoint() method of the endpoint
1244                  * itself directly.
1245                  */
1246                 protected abstract EdgeEndPoint getNextEndPoint(EdgeEndPoint endpoint);
1247
1248                 /**
1249                  * Provided endpoint is an endpoint of this endpoint, get the previous
1250                  * endpoint, either on this same endpoint, or or the connected endpoint.
1251                  * Note that you should use the getPreviousEndPoint() method of the endpoint
1252                  * itself directly.
1253                  */
1254                 protected abstract EdgeEndPoint getPreviousEndPoint(EdgeEndPoint endpoint);
1255
1256
1257                 /**
1258                  * An edge endpoint is where an edge can connect.
1259                  */
1260                 public class EdgeEndPoint {
1261                         private EdgeEndPoint() {
1262                         }
1263
1264                         /**
1265                          * Get the next endpoint. If this endpoint is an "in" endpoint,
1266                          * returns the corresponding "out" endpoint. If this endpoint
1267                          * is an "out" endpoint, return the connected endpoint if there is
1268                          * one, otherwise return null.
1269                          */
1270                         public EdgeEndPoint getNextEndPoint() {
1271                                 return element.getNextEndPoint(this);
1272                         }
1273
1274
1275                         /**
1276                          * Same as getNextEndPoint(), but with the previous endpoint.
1277                          */
1278                         public EdgeEndPoint getPreviousEndPoint() {
1279                                 return element.getPreviousEndPoint(this);
1280                         }
1281
1282
1283                         /**
1284                          * Get the position on the endpoint where this endpoint is.
1285                          */
1286                         public EdgeEndPointPosition getPosition() {
1287                                 return element.getPositionFromEndPoint(this);
1288                         }
1289
1290
1291                         private EdgeEndPoint otherEndPoint;
1292
1293                         /**
1294                          * Returns the endpoint on which this edge endpoint is.
1295                          */
1296                         public RNATemplateElement getElement() {
1297                                 return element;
1298                         }
1299
1300                         /**
1301                          * Returns the other endpoint of the edge.
1302                          * Will be null if there is no edge connecter to this endpoint.
1303                          */
1304                         public EdgeEndPoint getOtherEndPoint() {
1305                                 return otherEndPoint;
1306                         }
1307                         /**
1308                          * Returns the endpoint at the other endpoint of the edge.
1309                          * Will be null if there is no edge connecter to this endpoint.
1310                          */
1311                         public RNATemplateElement getOtherElement() {
1312                                 return (otherEndPoint != null) ? otherEndPoint.getElement() : null;
1313                         }
1314
1315                         /**
1316                          * Disconnect this endpoint from the other, ie. delete the edge
1317                          * between them. Note that this will modify both endpoints, and that
1318                          * x.disconnect() is equivalent to x.getOtherEndPoint().disconnect().
1319                          * If this endpoint is not connected, does nothing.
1320                          */
1321                         public void disconnect() {
1322                                 if (otherEndPoint != null) {
1323                                         otherEndPoint.otherEndPoint = null;
1324                                         otherEndPoint = null;
1325                                 }
1326                         }
1327
1328                         /**
1329                          * Tells whether this endpoint is connected with an edge to
1330                          * an other endpoint.
1331                          */
1332                         public boolean isConnected() {
1333                                 return (otherEndPoint != null);
1334                         }
1335
1336
1337                         /**
1338                          * Create an edge between two edge endpoints.
1339                          * This is a symmetric operation and it will modify both endpoints.
1340                          * It means x.connectTo(y) is equivalent to y.connectTo(x).
1341                          * The edge endpoint must be free (ie. not yet connected).
1342                          * Also, elements connected together must belong to the same template.
1343                          */
1344                         public void connectTo(EdgeEndPoint otherEndPoint) throws ExceptionEdgeEndpointAlreadyConnected, ExceptionInvalidRNATemplate {
1345                                 if (this.otherEndPoint != null || otherEndPoint.otherEndPoint != null) {
1346                                         throw (new ExceptionEdgeEndpointAlreadyConnected());
1347                                 }
1348                                 if (template != otherEndPoint.getElement().getParentTemplate()) {
1349                                         throw (new ExceptionInvalidRNATemplate("Elements from different templates cannot be connected with each other."));
1350                                 }
1351                                 this.otherEndPoint = otherEndPoint;
1352                                 otherEndPoint.otherEndPoint = this;
1353                         }
1354
1355
1356                         public String toString() {
1357                                 return "Edge endpoint on element " + element.toString() + " at position " + getPosition().toString();
1358                         }
1359                 }
1360
1361
1362                 /**
1363                  * Get the EdgeEndPoint object corresponding to the the given
1364                  * position on this endpoint.
1365                  */
1366                 public abstract EdgeEndPoint getEndPointFromPosition(EdgeEndPointPosition position);
1367
1368
1369                 /**
1370                  * The inverse of getEndPointFromPosition.
1371                  */
1372                 public abstract EdgeEndPointPosition getPositionFromEndPoint(EdgeEndPoint endPoint);
1373
1374
1375                 /**
1376                  * Connect the endpoint at position positionHere of this endpoint
1377                  * to the otherEndPoint.
1378                  */
1379                 public void connectTo(
1380                                 EdgeEndPointPosition positionHere,
1381                                 EdgeEndPoint otherEndPoint)
1382                 throws ExceptionEdgeEndpointAlreadyConnected, ExceptionInvalidRNATemplate {
1383                         EdgeEndPoint endPointHere = getEndPointFromPosition(positionHere);
1384                         endPointHere.connectTo(otherEndPoint);
1385                 }
1386
1387                 /**
1388                  * Connect the endpoint at position positionHere of this endpoint
1389                  * to the endpoint of otherElement at position positionOnOtherElement.
1390                  * @throws ExceptionInvalidRNATemplate
1391                  * @throws ExceptionEdgeEndpointAlreadyConnected, ExceptionEdgeEndpointAlreadyConnected
1392                  */
1393                 public void connectTo(
1394                                 EdgeEndPointPosition positionHere,
1395                                 RNATemplateElement otherElement,
1396                                 EdgeEndPointPosition positionOnOtherElement)
1397                 throws ExceptionEdgeEndpointAlreadyConnected, ExceptionEdgeEndpointAlreadyConnected, ExceptionInvalidRNATemplate {
1398                         EdgeEndPoint otherEndPoint = otherElement.getEndPointFromPosition(positionOnOtherElement);
1399                         connectTo(positionHere, otherEndPoint);
1400                 }
1401
1402
1403         }
1404
1405
1406         /**
1407          * An helix in an RNA template.
1408          *
1409          * @author Raphael Champeimont
1410          */
1411         public class RNATemplateHelix extends RNATemplateElement {
1412                 /**
1413                  * Number of base pairs in the helix.
1414                  */
1415                 private int length;
1416
1417                 /**
1418                  * Position of the helix start point,
1419                  * ie. the middle in the line [x,y] where (x,y)
1420                  * x is the base at the IN1 edge endpoint and
1421                  * y is the base at the OUT2 edge endpoint.
1422                  */
1423                 private Point2D.Double startPosition;
1424
1425                 /**
1426                  * Position of the helix end point,
1427                  * ie. the middle in the line [x,y] where (x,y)
1428                  * x is the base at the OUT1 edge endpoint and
1429                  * y is the base at the IN2 edge endpoint.
1430                  */
1431                 private Point2D.Double endPosition;
1432
1433
1434                 /**
1435                  * Tells whether the helix is flipped.
1436                  */
1437                 private boolean flipped = false;
1438
1439                 public boolean isFlipped() {
1440                         return flipped;
1441                 }
1442
1443                 public void setFlipped(boolean flipped) {
1444                         this.flipped = flipped;
1445                 }
1446
1447                 /**
1448                  * For an helix, tells us whether IN1/OUT1 is the 5' strand
1449                  * (the first strand we meet if we follow the RNA sequence)
1450                  * or the 3' strand (the second we meet if we follow the RNA sequence).
1451                  * This information cannot be known locally, we need the complete
1452                  * template to compute it, see RNATemplate.computeIn1Is().
1453                  */
1454                 private In1Is in1Is = null;
1455
1456                 public In1Is getIn1Is() {
1457                         return in1Is;
1458                 }
1459
1460                 public void setIn1Is(In1Is in1Is) {
1461                         this.in1Is = in1Is;
1462                 }
1463
1464
1465
1466                 /**
1467                  * A string displayed on the helix.
1468                  */
1469                 private String caption = null;
1470
1471                 public String getCaption() {
1472                         return caption;
1473                 }
1474
1475                 public void setCaption(String caption) {
1476                         this.caption = caption;
1477                 }
1478
1479                 public boolean hasCaption() {
1480                         return caption != null;
1481                 }
1482
1483
1484
1485
1486                 /**
1487                  * If we go through all bases of the RNA from first to last,
1488                  * we will pass twice through this helix. On time, we arrive
1489                  * from in1, and leave by out2, and the other time we arrive from
1490                  * in2 and leave by out2.
1491                  * Whether we go through in1/out1 or in2/out2 the first time
1492                  * is written in the in1Is field.
1493                  */
1494                 private final EdgeEndPoint in1, out1, in2, out2;
1495                 private String _name;
1496
1497                 public RNATemplateHelix(String name) {
1498                         in1 = new EdgeEndPoint();
1499                         out1 = new EdgeEndPoint();
1500                         in2 = new EdgeEndPoint();
1501                         out2 = new EdgeEndPoint();
1502                         _name = name;
1503                 }
1504
1505
1506
1507
1508
1509                 public String toString() {
1510                         return "Helix    @" + Integer.toHexString(hashCode()) + " len=" + length + " caption=" + caption;
1511                 }
1512
1513                 public String getName()
1514                 {return ""+_name; }
1515
1516
1517
1518                 public int getLength() {
1519                         return length;
1520                 }
1521
1522                 public void setLength(int length) {
1523                         this.length = length;
1524                 }
1525
1526                 public Point2D.Double getStartPosition() {
1527                         return startPosition;
1528                 }
1529
1530                 public void setStartPosition(Point2D.Double startPosition) {
1531                         this.startPosition = startPosition;
1532                 }
1533
1534                 public Point2D.Double getEndPosition() {
1535                         return endPosition;
1536                 }
1537
1538                 public void setEndPosition(Point2D.Double endPosition) {
1539                         this.endPosition = endPosition;
1540                 }
1541
1542                 public EdgeEndPoint getIn1() {
1543                         return in1;
1544                 }
1545
1546                 public EdgeEndPoint getOut1() {
1547                         return out1;
1548                 }
1549
1550                 public EdgeEndPoint getIn2() {
1551                         return in2;
1552                 }
1553
1554                 public EdgeEndPoint getOut2() {
1555                         return out2;
1556                 }
1557
1558                 public void disconnectFromAny() {
1559                         getIn1().disconnect();
1560                         getIn2().disconnect();
1561                         getOut1().disconnect();
1562                         getOut2().disconnect();
1563                 }
1564
1565
1566                 protected EdgeEndPoint getNextEndPoint(EdgeEndPoint endpoint) {
1567                         if (endpoint == in1) {
1568                                 return out1;
1569                         } else if (endpoint == in2) {
1570                                 return out2;
1571                         } else {
1572                                 return endpoint.getOtherEndPoint();
1573                         }
1574                 }
1575
1576
1577                 protected EdgeEndPoint getPreviousEndPoint(EdgeEndPoint endpoint) {
1578                         if (endpoint == out1) {
1579                                 return in1;
1580                         } else if (endpoint == out2) {
1581                                 return in2;
1582                         } else {
1583                                 return endpoint.getOtherEndPoint();
1584                         }
1585                 }
1586
1587
1588                 public EdgeEndPoint getIn1EndPoint() {
1589                         return in1;
1590                 }
1591
1592                 public EdgeEndPoint getEndPointFromPosition(
1593                                 EdgeEndPointPosition position) {
1594                         switch (position) {
1595                         case IN1:
1596                                 return getIn1();
1597                         case IN2:
1598                                 return getIn2();
1599                         case OUT1:
1600                                 return getOut1();
1601                         case OUT2:
1602                                 return getOut2();
1603                         default:
1604                                 return null;
1605                         }
1606                 }
1607
1608                 public EdgeEndPointPosition getPositionFromEndPoint(
1609                                 EdgeEndPoint endPoint) {
1610                         if (endPoint == in1) {
1611                                 return EdgeEndPointPosition.IN1;
1612                         } else if (endPoint == in2) {
1613                                 return EdgeEndPointPosition.IN2;
1614                         } else if (endPoint == out1) {
1615                                 return EdgeEndPointPosition.OUT1;
1616                         } else if (endPoint == out2) {
1617                                 return EdgeEndPointPosition.OUT2;
1618                         } else {
1619                                 return null;
1620                         }
1621                 }
1622
1623
1624         }
1625
1626
1627
1628         /**
1629          * A sequence of non-paired bases in an RNA template.
1630          *
1631          * @author Raphael Champeimont
1632          */
1633         public class RNATemplateUnpairedSequence extends RNATemplateElement {
1634                 /**
1635                  * Number of (non-paired) bases.
1636                  */
1637                 private int length;
1638
1639                 private static final double defaultTangentVectorAngle  = Math.PI / 2;
1640                 private static final double defaultTangentVectorLength = 100;
1641
1642                 /**
1643                  * The sequence is drawn along a cubic Bezier curve.
1644                  * The curve can be defined by 2 vectors, one for the start of the line
1645                  * and the other for the end. They are the tangents to the line at
1646                  * the beginning and the end of the line.
1647                  * Each vector can be defined by its length and its absolute angle.
1648                  * The angles are given in radians.
1649                  */
1650                 private double inTangentVectorAngle   = defaultTangentVectorAngle,
1651                                inTangentVectorLength  = defaultTangentVectorLength,
1652                                outTangentVectorAngle  = defaultTangentVectorAngle,
1653                                outTangentVectorLength = defaultTangentVectorLength;
1654
1655
1656
1657
1658                 /**
1659                  * Position of the begginning (at the "in" endpoint) of the line.
1660                  * It is only useful when the sequence is not yet connected to an helix.
1661                  * (Otherwise we can deduce it from this helix position).
1662                  */
1663                 private Point2D.Double vertex5;
1664
1665                 /**
1666                  * Position of the end (at the "out" endpoint) of the line.
1667                  * It is only useful when the sequence is not yet connected to an helix.
1668                  * (Otherwise we can deduce it from this helix position).
1669                  */
1670                 private Point2D.Double vertex3;
1671
1672
1673                 public Point2D.Double getVertex5() {
1674                         return vertex5;
1675                 }
1676
1677                 public void setVertex5(Point2D.Double vertex5) {
1678                         this.vertex5 = vertex5;
1679                 }
1680
1681                 public Point2D.Double getVertex3() {
1682                         return vertex3;
1683                 }
1684
1685                 public void setVertex3(Point2D.Double vertex3) {
1686                         this.vertex3 = vertex3;
1687                 }
1688
1689
1690
1691
1692                 /**
1693                  * The helixes connected on both sides.
1694                  * They must be helixes because only helixes have absolute positions,
1695                  * and the positions of the starting and ending points of the sequence
1696                  * are those stored in the helixes.
1697                  */
1698                 private final EdgeEndPoint in, out;
1699
1700                 private String _name;
1701
1702                 public RNATemplateUnpairedSequence(String name) {
1703                         in = new EdgeEndPoint();
1704                         out = new EdgeEndPoint();
1705                         _name = name;
1706                 }
1707
1708
1709                 public String toString() {
1710                         return "Sequence @" + Integer.toHexString(hashCode()) + " len=" + length;
1711                 }
1712
1713                 public String getName()
1714                 {return ""+_name; }
1715
1716
1717
1718                 public int getLength() {
1719                         return length;
1720                 }
1721
1722                 public void setLength(int length) {
1723                         this.length = length;
1724                 }
1725
1726                 public double getInTangentVectorAngle() {
1727                         return inTangentVectorAngle;
1728                 }
1729
1730                 public void setInTangentVectorAngle(double inTangentVectorAngle) {
1731                         this.inTangentVectorAngle = inTangentVectorAngle;
1732                 }
1733
1734                 public double getInTangentVectorLength() {
1735                         return inTangentVectorLength;
1736                 }
1737
1738                 public void setInTangentVectorLength(double inTangentVectorLength) {
1739                         this.inTangentVectorLength = inTangentVectorLength;
1740                 }
1741
1742                 public double getOutTangentVectorAngle() {
1743                         return outTangentVectorAngle;
1744                 }
1745
1746                 public void setOutTangentVectorAngle(double outTangentVectorAngle) {
1747                         this.outTangentVectorAngle = outTangentVectorAngle;
1748                 }
1749
1750                 public double getOutTangentVectorLength() {
1751                         return outTangentVectorLength;
1752                 }
1753
1754                 public void setOutTangentVectorLength(double outTangentVectorLength) {
1755                         this.outTangentVectorLength = outTangentVectorLength;
1756                 }
1757
1758                 public EdgeEndPoint getIn() {
1759                         return in;
1760                 }
1761
1762                 public EdgeEndPoint getOut() {
1763                         return out;
1764                 }
1765
1766                 public void disconnectFromAny() {
1767                         getIn().disconnect();
1768                         getOut().disconnect();
1769                 }
1770
1771
1772                 protected EdgeEndPoint getNextEndPoint(EdgeEndPoint endpoint) {
1773                         if (endpoint == in) {
1774                                 return out;
1775                         } else {
1776                                 return endpoint.getOtherEndPoint();
1777                         }
1778                 }
1779
1780                 protected EdgeEndPoint getPreviousEndPoint(EdgeEndPoint endpoint) {
1781                         if (endpoint == out) {
1782                                 return in;
1783                         } else {
1784                                 return endpoint.getOtherEndPoint();
1785                         }
1786                 }
1787
1788                 public EdgeEndPoint getIn1EndPoint() {
1789                         return in;
1790                 }
1791
1792
1793                 public EdgeEndPoint getEndPointFromPosition(
1794                                 EdgeEndPointPosition position) {
1795                         switch (position) {
1796                         case IN1:
1797                                 return getIn();
1798                         case OUT1:
1799                                 return getOut();
1800                         default:
1801                                 return null;
1802                         }
1803                 }
1804
1805
1806                 public EdgeEndPointPosition getPositionFromEndPoint(
1807                                 EdgeEndPoint endPoint) {
1808                         if (endPoint == in) {
1809                                 return EdgeEndPointPosition.IN1;
1810                         } else if (endPoint == out) {
1811                                 return EdgeEndPointPosition.OUT1;
1812                         } else {
1813                                 return null;
1814                         }
1815                 }
1816
1817
1818         }
1819
1820
1821 }