src2/fr/orsay/lri/varna/models/treealign/RNATree.java

   1 package fr.orsay.lri.varna.models.treealign;
   2
   3 import java.util.ArrayList;
   4 import java.util.List;
   5
   6 import fr.orsay.lri.varna.exceptions.MappingException;
   7 import fr.orsay.lri.varna.models.rna.Mapping;
   8 import fr.orsay.lri.varna.models.rna.ModeleBase;
   9 import fr.orsay.lri.varna.models.rna.ModeleBaseNucleotide;
  10 import fr.orsay.lri.varna.models.rna.ModeleBP;
  11 import fr.orsay.lri.varna.models.rna.RNA;
  12
  13
  14
  15 /**
  16  * This class contains all functions that are specific to trees
  17  * (class Tree) of RNA.
  18  *
  19  * @author Raphael Champeimont
  20  *
  21  */
  22 public class RNATree {
  23         /**
  24          * Convert an RNA object into a RNA tree.
  25          * The root node will have a null value because it is a fake
  26          * node added to have a tree (otherwise we would have a forest).
  27          */
  28         public static Tree<RNANodeValue> RNATreeFromRNA(RNA rna) {
  29                 ConvertToTree converter = new ConvertToTree(rna);
  30                 return converter.toTreeAux(0);
  31         }
  32
  33         private static class ConvertToTree {
  34                 private RNA rna;
  35
  36                 private int i = 0;
  37
  38                 /** Starts at the current position i in the sequence and converts the sequence
  39                  *  to a tree.
  40                  * @return the created tree
  41                  */
  42                 public Tree<RNANodeValue> toTreeAux(int depth) {
  43                         Tree<RNANodeValue> tree = new Tree<RNANodeValue>();
  44                         List<Tree<RNANodeValue>> children = tree.getChildren();
  45                         // No value because it is a fake root
  46                         tree.setValue(null);
  47
  48                         int length = rna.getSize();
  49                         while (i < length) {
  50                                 ModeleBase base = rna.getBaseAt(i);
  51                                 int indexOfAssociatedBase = base.getElementStructure();
  52                                 if (indexOfAssociatedBase >= 0) {
  53                                         if (indexOfAssociatedBase > i) {
  54                                                 // left parenthesis, we must analyze the children
  55                                                 RNANodeValue childValue = new RNANodeValue();
  56                                                 childValue.setLeftBasePosition(i);
  57                                                 childValue.setRightBasePosition(indexOfAssociatedBase);
  58                                                 childValue.setOrigin(RNANodeValue.Origin.BASE_PAIR_FROM_HELIX);
  59
  60                                                 if (base instanceof ModeleBaseNucleotide) {
  61                                                         childValue.setLeftNucleotide(((ModeleBaseNucleotide) base).getBase());
  62                                                         childValue.setRightNucleotide(((ModeleBaseNucleotide) rna.getBaseAt(indexOfAssociatedBase)).getBase());
  63                                                 }
  64                                                 i++;
  65                                                 Tree<RNANodeValue> child = toTreeAux(depth+1);
  66                                                 child.setValue(childValue);
  67                                                 children.add(child);
  68                                         } else {
  69                                                 // right parenthesis, we have finished analyzing the children
  70                                                 i++;
  71                                                 break;
  72                                         }
  73                                 } else {
  74                                         // we have a non-paired base
  75                                         Tree<RNANodeValue> child = new Tree<RNANodeValue>();
  76                                         RNANodeValue childValue = new RNANodeValue();
  77                                         childValue.setLeftBasePosition(i);
  78                                         if (base instanceof ModeleBaseNucleotide) {
  79                                                 childValue.setLeftNucleotide(((ModeleBaseNucleotide) base).getBase());
  80                                         }
  81
  82                                         // Even in this case (getElementStructure() < 0)
  83                                         // this base may still come from an helix which may have
  84                                         // been broken to remove a pseudoknot.
  85                                         childValue.setOrigin(RNANodeValue.Origin.BASE_FROM_UNPAIRED_REGION);
  86                                         ArrayList<ModeleBP> auxBasePairs = rna.getAuxBPs(i);
  87                                         for (ModeleBP auxBasePair: auxBasePairs) {
  88                                                 if (auxBasePair.isCanonical()) {
  89                                                         int partner5 = ((ModeleBaseNucleotide) auxBasePair.getPartner5()).getIndex();
  90                                                         int partner3 = ((ModeleBaseNucleotide) auxBasePair.getPartner3()).getIndex();
  91                                                         if (i == partner5) {
  92                                                                 childValue.setOrigin(RNANodeValue.Origin.BASE_FROM_HELIX_STRAND5);
  93                                                         } else if (i == partner3) {
  94                                                                 childValue.setOrigin(RNANodeValue.Origin.BASE_FROM_HELIX_STRAND3);
  95                                                         } else {
  96                                                                 System.err.println("Warning: Base index is " + i + " but neither endpoint matches it (edge endpoints are " + partner5 + " and " + partner3 + ").");
  97                                                         }
  98
  99                                                 }
 100                                         }
 101
 102                                         child.setValue(childValue);
 103                                         children.add(child);
 104                                         i++;
 105                                 }
 106                         }
 107
 108                         return tree;
 109                 }
 110
 111                 public ConvertToTree(RNA rna) {
 112                         this.rna = rna;
 113                 }
 114         }
 115
 116
 117         /**
 118          * Convert an RNA tree alignment into a Mapping.
 119          */
 120         public static Mapping mappingFromAlignment(Tree<AlignedNode<RNANodeValue,RNANodeValue>> alignment) throws MappingException {
 121                 ConvertToMapping converter = new ConvertToMapping();
 122                 return converter.convert(alignment);
 123         }
 124
 125         private static class ConvertToMapping {
 126                 private Mapping m;
 127
 128                 public Mapping convert(Tree<AlignedNode<RNANodeValue,RNANodeValue>> tree) throws MappingException {
 129                         m = new Mapping();
 130                         convertSubTree(tree);
 131                         return m;
 132                 }
 133
 134                 private void convertSubTree(Tree<AlignedNode<RNANodeValue,RNANodeValue>> tree) throws MappingException {
 135                         AlignedNode<RNANodeValue,RNANodeValue> alignedNode = tree.getValue();
 136                         Tree<RNANodeValue> leftNode  = alignedNode.getLeftNode();
 137                         Tree<RNANodeValue> rightNode = alignedNode.getRightNode();
 138                         if (leftNode != null && rightNode != null) {
 139                                 RNANodeValue v1 = leftNode.getValue();
 140                                 RNANodeValue v2 = rightNode.getValue();
 141                                 int l1 = v1.getLeftBasePosition();
 142                                 int r1 = v1.getRightBasePosition();
 143                                 int l2 = v2.getLeftBasePosition();
 144                                 int r2 = v2.getRightBasePosition();
 145                                 if (l1 >= 0 && l2 >= 0) {
 146                                         m.addCouple(l1, l2);
 147                                 }
 148                                 if (r1 >= 0 && r2 >= 0) {
 149                                         m.addCouple(r1, r2);
 150                                 }
 151                         }
 152                         for (Tree<AlignedNode<RNANodeValue,RNANodeValue>> child: tree.getChildren()) {
 153                                 convertSubTree(child);
 154                         }
 155                 }
 156         }
 157
 158 }