1 package fr.orsay.lri.varna.models.treealign;
3 import java.util.ArrayList;
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;
16 * This class contains all functions that are specific to trees
17 * (class Tree) of RNA.
19 * @author Raphael Champeimont
22 public class RNATree {
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).
28 public static Tree<RNANodeValue> RNATreeFromRNA(RNA rna) {
29 ConvertToTree converter = new ConvertToTree(rna);
30 return converter.toTreeAux(0);
33 private static class ConvertToTree {
38 /** Starts at the current position i in the sequence and converts the sequence
40 * @return the created tree
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
48 int length = rna.getSize();
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);
60 if (base instanceof ModeleBaseNucleotide) {
61 childValue.setLeftNucleotide(((ModeleBaseNucleotide) base).getBase());
62 childValue.setRightNucleotide(((ModeleBaseNucleotide) rna.getBaseAt(indexOfAssociatedBase)).getBase());
65 Tree<RNANodeValue> child = toTreeAux(depth+1);
66 child.setValue(childValue);
69 // right parenthesis, we have finished analyzing the children
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());
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();
92 childValue.setOrigin(RNANodeValue.Origin.BASE_FROM_HELIX_STRAND5);
93 } else if (i == partner3) {
94 childValue.setOrigin(RNANodeValue.Origin.BASE_FROM_HELIX_STRAND3);
96 System.err.println("Warning: Base index is " + i + " but neither endpoint matches it (edge endpoints are " + partner5 + " and " + partner3 + ").");
102 child.setValue(childValue);
111 public ConvertToTree(RNA rna) {
118 * Convert an RNA tree alignment into a Mapping.
120 public static Mapping mappingFromAlignment(Tree<AlignedNode<RNANodeValue,RNANodeValue>> alignment) throws MappingException {
121 ConvertToMapping converter = new ConvertToMapping();
122 return converter.convert(alignment);
125 private static class ConvertToMapping {
128 public Mapping convert(Tree<AlignedNode<RNANodeValue,RNANodeValue>> tree) throws MappingException {
130 convertSubTree(tree);
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) {
148 if (r1 >= 0 && r2 >= 0) {
152 for (Tree<AlignedNode<RNANodeValue,RNANodeValue>> child: tree.getChildren()) {
153 convertSubTree(child);