1 package fr.orsay.lri.varna.models.treealign;
2 import java.util.ArrayList;
3 import java.util.LinkedList;
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;
12 * This class contains all functions that are specific to trees
13 * (class Tree) of RNA, with RNANodeValue2.
15 * @author Raphael Champeimont
18 public class RNATree2 {
20 * Convert an RNA object into a RNA tree with RNANodeValue2.
21 * @throws RNATree2Exception
23 public static Tree<RNANodeValue2> RNATree2FromRNA(RNA rna) throws RNATree2Exception {
24 Tree<RNANodeValue> fullTree = RNATree.RNATreeFromRNA(rna);
25 return RNATree2FromRNATree(fullTree);
29 * Convert from RNANodeValue model to RNANodeValue2 model,
30 * ie. compact consecutive non-paired bases.
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()));
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();
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) {
58 if (originalTree.getChildren().size() > 0) {
59 throw (new RNATree2Exception("Non-paired base cannot have children."));
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
67 // if we have gathered some non-paired bases, add a node with
69 RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
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);
78 case BASE_FROM_UNPAIRED_REGION:
79 consecutiveNonPairedBases.add(originalTree.getValue());
81 case BASE_PAIR_FROM_HELIX:
82 throw (new RNATree2Exception("Origin is BASE_PAIR_FROM_HELIX but this is not a pair."));
87 // if we have gathered some non-paired bases, add a node with
89 RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
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);
101 // if there we have some non-paired bases, add them grouped
102 RNAForest2FromRNAForestCommitNonPaired(forest, consecutiveNonPairedBases);
109 * Convert an RNA tree (with RNANodeValue2) alignment into a Mapping.
111 public static Mapping mappingFromAlignment(Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> alignment) throws MappingException {
112 ConvertToMapping converter = new ConvertToMapping();
113 return converter.convert(alignment);
116 private static class ConvertToMapping {
118 ExampleDistance3 sequenceAligner = new ExampleDistance3();
120 public Mapping convert(Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> tree) throws MappingException {
122 convertSubTree(tree);
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) {
145 if (r1 >= 0 && r2 >= 0) {
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();
167 for (Tree<AlignedNode<RNANodeValue2,RNANodeValue2>> child: tree.getChildren()) {
168 convertSubTree(child);