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

   1 package fr.orsay.lri.varna.models.treealign;
   2 import java.util.ArrayList;
   3 import java.util.LinkedList;
   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.RNA;
   9
  10
  11 /**
  12  * This class contains all functions that are specific to trees
  13  * (class Tree) of RNA, with RNANodeValue2.
  14  *
  15  * @author Raphael Champeimont
  16  *
  17  */
  18 public class RNATree2 {
  19         /**
  20          * Convert an RNA object into a RNA tree with RNANodeValue2.
  21          * @throws RNATree2Exception
  22          */
  23         public static Tree<RNANodeValue2> RNATree2FromRNA(RNA rna) throws RNATree2Exception {
  24                 Tree<RNANodeValue> fullTree = RNATree.RNATreeFromRNA(rna);
  25                 return RNATree2FromRNATree(fullTree);
  26         }
  27
  28         /**
  29          * Convert from RNANodeValue model to RNANodeValue2 model,
  30          * ie. compact consecutive non-paired bases.
  31          */
  32         public static Tree<RNANodeValue2> RNATree2FromRNATree(Tree<RNANodeValue> originalTree) throws RNATree2Exception {
  33                 Tree<RNANodeValue2> newTree = new Tree<RNANodeValue2>();
  34                 // Root in original tree is fake, so make a fake root
  35                 newTree.setValue(null);
  36                 newTree.replaceChildrenListBy(RNAForest2FromRNAForest(originalTree.getChildren()));
  37                 return newTree;
  38         }
  39
  40         private static void RNAForest2FromRNAForestCommitNonPaired(List<Tree<RNANodeValue2>> forest, List<RNANodeValue> consecutiveNonPairedBases) {
  41                 // add the group of non-paired bases if there is one
  42                 if (consecutiveNonPairedBases.size() > 0) {
  43                         RNANodeValue2 groupOfConsecutiveBases = new RNANodeValue2(false);
  44                         groupOfConsecutiveBases.getNodes().addAll(consecutiveNonPairedBases);
  45                         Tree<RNANodeValue2> groupOfConsecutiveBasesNode = new Tree<RNANodeValue2>();
  46                         groupOfConsecutiveBasesNode.setValue(groupOfConsecutiveBases);
  47                         forest.add(groupOfConsecutiveBasesNode);
  48                         consecutiveNonPairedBases.clear();
  49                 }
  50         }
  51
  52         private static List<Tree<RNANodeValue2>> RNAForest2FromRNAForest(List<Tree<RNANodeValue>> originalForest) throws RNATree2Exception {
  53                 List<Tree<RNANodeValue2>> forest = new ArrayList<Tree<RNANodeValue2>>();
  54                 List<RNANodeValue> consecutiveNonPairedBases = new LinkedList<RNANodeValue>();
  55                 for (Tree<RNANodeValue> originalTree: originalForest) {
  56                         if (originalTree.getValue().getRightBasePosition() == -1) {
  57                                 // non-paired base
  58                                 if (originalTree.getChildren().size() > 0) {
  59                                         throw (new RNATree2Exception("Non-paired base cannot have children."));
  60                                 }
  61
  62                                 switch (originalTree.getValue().getOrigin()) {
  63                                 case BASE_FROM_HELIX_STRAND5:
  64                                 case BASE_FROM_HELIX_STRAND3:
  65                                         // This base is part of a broken base pair
  66
  67                                         // if we have gathered some non-paired bases, add a node with
  68                                         // the group of them
  69                                         RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
  70
  71                                         // now add the node
  72                                         RNANodeValue2 pairedBase = new RNANodeValue2(true);
  73                                         pairedBase.setNode(originalTree.getValue());
  74                                         Tree<RNANodeValue2> pairedBaseNode = new Tree<RNANodeValue2>();
  75                                         pairedBaseNode.setValue(pairedBase);
  76                                         forest.add(pairedBaseNode);
  77                                         break;
  78                                 case BASE_FROM_UNPAIRED_REGION:
  79                                         consecutiveNonPairedBases.add(originalTree.getValue());
  80                                         break;
  81                                 case BASE_PAIR_FROM_HELIX:
  82                                         throw (new RNATree2Exception("Origin is BASE_PAIR_FROM_HELIX but this is not a pair."));
  83                                 }
  84                         } else {
  85                                 // paired bases
  86
  87                                 // if we have gathered some non-paired bases, add a node with
  88                                 // the group of them
  89                                 RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
  90
  91                                 // now add the node
  92                                 RNANodeValue2 pairedBase = new RNANodeValue2(true);
  93                                 pairedBase.setNode(originalTree.getValue());
  94                                 Tree<RNANodeValue2> pairedBaseNode = new Tree<RNANodeValue2>();
  95                                 pairedBaseNode.setValue(pairedBase);
  96                                 pairedBaseNode.replaceChildrenListBy(RNAForest2FromRNAForest(originalTree.getChildren()));
  97                                 forest.add(pairedBaseNode);
  98                         }
  99                 }
 100
 101                 // if there we have some non-paired bases, add them grouped
 102                 RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
 103
 104                 return forest;
 105         }
 106
 107
 108         /**
 109          * Convert an RNA tree (with RNANodeValue2) alignment into a Mapping.
 110          */
 111         public static Mapping mappingFromAlignment(Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> alignment) throws MappingException {
 112                 ConvertToMapping converter = new ConvertToMapping();
 113                 return converter.convert(alignment);
 114         }
 115
 116         private static class ConvertToMapping {
 117                 private Mapping m;
 118                 ExampleDistance3 sequenceAligner = new ExampleDistance3();
 119
 120                 public Mapping convert(Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> tree) throws MappingException {
 121                         m = new Mapping();
 122                         convertSubTree(tree);
 123                         return m;
 124                 }
 125
 126                 private void convertSubTree(Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> tree) throws MappingException {
 127                         AlignedNode<RNANodeValue2,RNANodeValue2> alignedNode = tree.getValue();
 128                         Tree<RNANodeValue2> leftNode  = alignedNode.getLeftNode();
 129                         Tree<RNANodeValue2> rightNode = alignedNode.getRightNode();
 130                         if (leftNode != null && rightNode != null) {
 131                                 RNANodeValue2 v1 = leftNode.getValue();
 132                                 RNANodeValue2 v2 = rightNode.getValue();
 133                                 if (v1.isSingleNode() && v2.isSingleNode()) {
 134                                         // we have aligned (x,y) with (x',y')
 135                                         // so we map x with x' and y with y'
 136                                         RNANodeValue vsn1 = v1.getNode();
 137                                         RNANodeValue vsn2 = v2.getNode();
 138                                         int l1 = vsn1.getLeftBasePosition();
 139                                         int r1 = vsn1.getRightBasePosition();
 140                                         int l2 = vsn2.getLeftBasePosition();
 141                                         int r2 = vsn2.getRightBasePosition();
 142                                         if (l1 >= 0 && l2 >= 0) {
 143                                                 m.addCouple(l1, l2);
 144                                         }
 145                                         if (r1 >= 0 && r2 >= 0) {
 146                                                 m.addCouple(r1, r2);
 147                                         }
 148                                 } else if (!v1.isSingleNode() && !v2.isSingleNode()) {
 149                                         // We have aligned x1 x2 ... xn with y1 y2 ... ym.
 150                                         // So we will now (re-)compute this sequence alignment.
 151                                         int[][] sequenceAlignment = sequenceAligner.alignSequenceNodes(v1, v2).getAlignment();
 152                                         int l = sequenceAlignment[0].length;
 153                                         for (int i=0; i<l; i++) {
 154                                                 // b1 and b2 are indexes in the aligned sequences
 155                                                 int b1 = sequenceAlignment[0][i];
 156                                                 int b2 = sequenceAlignment[1][i];
 157                                                 if (b1 != -1 && b2 != -1) {
 158                                                         int l1 = v1.getNodes().get(b1).getLeftBasePosition();
 159                                                         int l2 = v2.getNodes().get(b2).getLeftBasePosition();
 160                                                         m.addCouple(l1, l2);
 161                                                 }
 162                                         }
 163
 164                                 }
 165                         }
 166
 167                         for (Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> child: tree.getChildren()) {
 168                                 convertSubTree(child);
 169                         }
 170                 }
 171         }
 172 }