1 package fr.orsay.lri.varna.models.rna;
3 import java.awt.Rectangle;
5 import java.awt.geom.AffineTransform;
6 import java.awt.geom.Area;
7 import java.awt.geom.GeneralPath;
8 import java.awt.geom.PathIterator;
9 import java.awt.geom.Point2D;
10 import java.awt.geom.Rectangle2D;
11 import java.lang.reflect.Array;
12 import java.util.ArrayList;
13 import java.util.Arrays;
14 import java.util.LinkedList;
15 import java.util.Random;
16 import java.util.Stack;
17 import java.util.Vector;
19 import fr.orsay.lri.varna.VARNAPanel;
21 public class VARNASecDraw {
22 public static VARNAPanel _vp = null;
25 public abstract class Portion
27 public abstract ArrayList<Integer> getBaseList();
28 public abstract int getNumBases();
29 public abstract GeneralPath getOutline(RNA r);
33 public class UnpairedPortion extends Portion
37 public UnpairedPortion(int pos, int len)
43 public ArrayList<Integer> getBaseList() {
44 // TODO Auto-generated method stub
47 public String toString()
49 return "U["+_pos+","+(_pos+_len-1)+"]";
52 public int getNumBases() {
57 public GeneralPath getOutline(RNA r) {
59 GeneralPath gp = new GeneralPath();
60 ArrayList<ModeleBase> l = r.get_listeBases();
61 Point2D.Double p0 = l.get(_pos).getCoords();
62 gp.moveTo((float)p0.x, (float)p0.y);
63 for (int i=1;i<_len;i++)
65 Point2D.Double p = l.get(_pos+i).getCoords();
66 gp.lineTo((float)p.x, (float)p.y);
72 public class PairedPortion extends Portion
79 public PairedPortion(int pos1,int pos2, int len, RNATree r)
88 public ArrayList<Integer> getBaseList() {
89 // TODO Auto-generated method stub
93 public String toString()
95 return "H["+_pos1+","+(_pos1+_len-1)+"]["+(_pos2-_len+1)+","+(_pos2)+"]\n"+_r.toString();
99 public int getNumBases() {
103 public GeneralPath getLocalOutline(RNA r) {
104 GeneralPath gp = new GeneralPath();
107 ArrayList<ModeleBase> l = r.get_listeBases();
108 Point2D.Double p1 = l.get(_pos1).getCoords();
109 Point2D.Double p2 = l.get(_pos1+_len-1).getCoords();
110 Point2D.Double p3 = l.get(_pos2-_len+1).getCoords();
111 Point2D.Double p4 = l.get(_pos2).getCoords();
112 gp.moveTo((float)p1.x, (float)p1.y);
113 gp.lineTo((float)p2.x, (float)p2.y);
114 gp.lineTo((float)p3.x, (float)p3.y);
115 gp.lineTo((float)p4.x, (float)p4.y);
121 public GeneralPath getOutline(RNA r) {
122 return getOutline(r,false);
125 public GeneralPath getOutline(RNA r, boolean local) {
126 ArrayList<ModeleBase> l = r.get_listeBases();
127 Point2D.Double p1 = l.get(_pos1).getCoords();
128 Point2D.Double p2 = l.get(_pos1+_len-1).getCoords();
129 Point2D.Double p3 = l.get(_pos2-_len+1).getCoords();
130 Point2D.Double p4 = l.get(_pos2).getCoords();
131 GeneralPath gp = new GeneralPath();
132 gp.moveTo((float)p1.x, (float)p1.y);
133 gp.lineTo((float)p2.x, (float)p2.y);
135 gp.append(_r.getOutline(r), true);
136 gp.lineTo((float)p3.x, (float)p3.y);
137 gp.lineTo((float)p4.x, (float)p4.y);
143 public int _depth = 0;
148 ArrayList<Portion> _portions = new ArrayList<Portion>();
149 int _numPairedPortions=0;
156 public void addPortion(Portion p)
159 if (p instanceof PairedPortion)
161 _numPairedPortions++;
165 public int getNumPortions()
167 return _portions.size();
170 public Portion getPortion(int i)
172 return _portions.get(i);
175 public String toString()
179 for (int i=0;i<_portions.size();i++ )
181 result += String.format("%1$#" + _depth + "s", ' ');
182 result += _portions.get(i).toString();
183 if (i<_portions.size()-1)
190 public GeneralPath getOutline(RNA r) {
191 GeneralPath result = new GeneralPath();
192 for (int i=0;i<_portions.size();i++)
194 result.append(_portions.get(i).getOutline(r),true);
201 private void buildTree(int i, int j, RNATree parent, RNA r)
203 //LinkedList<BuildTreeArgs> s = new LinkedList<BuildTreeArgs>();
204 //s.add(new BuildTreeArgs(xi, xj, xparent,xr));
208 //BuildTreeArgs a = s.removeLast();
210 parent.addPortion(new UnpairedPortion(i,j-i+1));
213 if (r.get_listeBases().get(i).getElementStructure() == j)
217 boolean over = false;
218 while( (i+1<r.get_listeBases().size()) && (j-1>=0)&& (i+1<=j-1) && !over)
220 if (r.get_listeBases().get(i).getElementStructure() != j)
227 RNATree t = new RNATree();
229 buildTree(i2,j2,t,r);
230 PairedPortion p = new PairedPortion(i1,j1,i2-i1,t);
231 parent.addPortion(p);
239 l = r.get_listeBases().get(k).getElementStructure();
243 { parent.addPortion(new UnpairedPortion(start,len)); }
244 buildTree(k, l, parent, r);
255 parent.addPortion(new UnpairedPortion(start,len));
261 public void drawTree(double x0, double y0, RNATree t, double dir, RNA r, double straightness)
263 boolean collision = true;
266 double multRadius = 1.0;
267 double initCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
268 for (int i=0;i<t.getNumPortions();i++ )
270 Portion p = t.getPortion(i);
271 if (p instanceof PairedPortion)
273 initCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
277 initCirc += r.LOOP_DISTANCE*(p.getNumBases());
282 double totCirc = r.BASE_PAIR_DISTANCE+straightness*r.LOOP_DISTANCE;
283 for (int i=0;i<t.getNumPortions();i++ )
285 Portion p = t.getPortion(i);
286 if (p instanceof PairedPortion)
288 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
293 if ((i==0) || (i==t.getNumPortions()-1))
295 totCirc += mod*r.LOOP_DISTANCE*(p.getNumBases());
298 double radius = multRadius*initCirc/(2.0*Math.PI);
300 x = x0+radius*Math.cos(dir+Math.PI);
301 y = y0+radius*Math.sin(dir+Math.PI);
303 double angleIncr = (2.0*Math.PI)/(totCirc);
304 double circ = r.BASE_PAIR_DISTANCE/2.0+straightness*r.LOOP_DISTANCE;
306 ArrayList<GeneralPath> shapes = new ArrayList<GeneralPath>();
307 for (int i=0;i<t.getNumPortions();i++ )
309 Portion p = t.getPortion(i);
310 if (p instanceof PairedPortion)
312 circ+=r.BASE_PAIR_DISTANCE/2.0;
313 ndir = dir + circ*angleIncr;
314 PairedPortion pp = (PairedPortion) p;
315 for(int j=0;j<pp._len;j++)
319 double vx = Math.cos(ndir);
320 double vy = Math.sin(ndir);
321 double nx = x+((j*r.LOOP_DISTANCE+radius)*vx);
322 double ny = y+((j*r.LOOP_DISTANCE+radius)*vy);
323 r.get_listeBases().get(i1).set_coords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
324 r.get_listeBases().get(i2).set_coords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
326 double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
327 double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
328 drawTree(nx, ny, pp._r, ndir+Math.PI, r, straightness);
329 shapes.add(pp.getOutline(r));
330 circ += r.LOOP_DISTANCE + r.BASE_PAIR_DISTANCE/2.0;
332 else if (p instanceof UnpairedPortion)
334 UnpairedPortion up = (UnpairedPortion) p;
336 if ((i==0) || (i==t.getNumPortions()-1))
338 for(int j=0;j<up._len;j++)
340 ndir = dir + circ*angleIncr;
341 double vx = Math.cos(ndir);
342 double vy = Math.sin(ndir);
343 double nx = x+((radius)*vx);
344 double ny = y+((radius)*vy);
345 r.get_listeBases().get(up._pos+j).set_coords(new Point2D.Double(nx,ny));
346 circ += mod*r.LOOP_DISTANCE;
349 //System.out.println(dir);
351 circ += r.BASE_PAIR_DISTANCE/2.0;
352 System.out.println(""+circ+"/"+totCirc);
356 for (int i=0;(i<shapes.size()) && !collision;i++)
358 Area a1 = new Area(shapes.get(i));
359 for (int j=i+1;(j<shapes.size())&& !collision;j++)
361 Area a2 = new Area(shapes.get(j));
384 public int[] nextPlacement(int[] p) throws Exception
386 //System.out.println(Arrays.toString(p));
388 int prev = MAX_NUM_DIR;
389 boolean stop = false;
390 while((i>=0) && !stop)
401 throw new Exception("No more placement available");
409 //System.out.println(Arrays.toString(p));
414 public void drawTree(double x0, double y0, RNATree t, double dir, RNA r) throws Exception
416 boolean collision = true;
422 double totCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
423 for (int i=0;i<t.getNumPortions();i++ )
425 Portion p = t.getPortion(i);
426 if (p instanceof PairedPortion)
428 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
433 totCirc += r.LOOP_DISTANCE*(p.getNumBases());
434 nbUn += p.getNumBases()+1;
437 double radius = r.determineRadius(nbHel, nbUn, totCirc/(2.0*Math.PI));
439 for (int i=0;i<t.getNumPortions();i++ )
441 Portion p = t.getPortion(i);
442 if (p instanceof PairedPortion)
447 int[] placement = new int[numHelices];
448 double inc = ((double)MAX_NUM_DIR)/((double)numHelices+1);
450 for (int i=0;i<numHelices;i++ )
452 placement[i] = (int)Math.round(val);
455 System.out.println();
456 double angleIncr = 2.0*Math.PI/(double)MAX_NUM_DIR;
459 x = x0+radius*Math.cos(dir+Math.PI);
460 y = y0+radius*Math.sin(dir+Math.PI);
461 ArrayList<GeneralPath> shapes = new ArrayList<GeneralPath>();
463 for (int i=0;i<t.getNumPortions();i++ )
465 Portion p = t.getPortion(i);
466 if (p instanceof PairedPortion)
468 double ndir = dir + placement[curH]*angleIncr;
470 PairedPortion pp = (PairedPortion) p;
471 for(int j=0;j<pp._len;j++)
475 double vx = Math.cos(ndir);
476 double vy = Math.sin(ndir);
477 double nx = x+(((j)*r.LOOP_DISTANCE+radius)*vx);
478 double ny = y+(((j)*r.LOOP_DISTANCE+radius)*vy);
479 r.get_listeBases().get(i1).setCoords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
480 r.get_listeBases().get(i2).setCoords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
482 double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
483 double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
484 drawTree(nx, ny, pp._r, ndir+Math.PI, r);
485 shapes.add(pp.getOutline(r));
487 else if (p instanceof UnpairedPortion)
489 UnpairedPortion up = (UnpairedPortion) p;
490 for(int j=0;j<up._len;j++)
492 /*ndir = dir + circ*angleIncr;
493 double vx = Math.cos(ndir);
494 double vy = Math.sin(ndir);
495 double nx = x+((radius)*vx);
496 double ny = y+((radius)*vy);
497 r.get_listeBases().get(up._pos+j).set_coords(new Point2D.Double(nx,ny));
498 circ += mod*r.LOOP_DISTANCE;*/
499 r.get_listeBases().get(up._pos+j).setCoords(new Point2D.Double(x,y));
502 //System.out.println(dir);
507 for (int i=0;(i<shapes.size()) && !collision;i++)
509 Area a1 = new Area(shapes.get(i));
510 for (int j=i+1;(j<shapes.size())&& !collision;j++)
512 Area a2 = new Area(shapes.get(j));
522 placement = nextPlacement(placement);
534 private class HelixEmbedding
536 private GeneralPath _clip;
537 Point2D.Double _support;
538 ArrayList<HelixEmbedding> _children = new ArrayList<HelixEmbedding>();
539 ArrayList<Integer> _indices = new ArrayList<Integer>();
542 HelixEmbedding _parent;
544 public HelixEmbedding(Point2D.Double support, PairedPortion p, RNA r, HelixEmbedding parent)
547 _clip = p.getLocalOutline(r);
553 public void addHelixEmbedding(HelixEmbedding h, int index)
559 public GeneralPath getShape()
565 public int chooseNextMove()
567 int i = _parent._children.indexOf(this);
570 if (_parent._children.size()<VARNASecDraw.MAX_NUM_DIR-1)
572 if (_parent._children.size()==1)
573 { min=1;max=VARNASecDraw.MAX_NUM_DIR-1; }
579 { min = _parent._indices.get(i-1)+1;}
580 if (i==_parent._children.size()-1)
581 { max = VARNASecDraw.MAX_NUM_DIR-1; }
583 { max = _parent._indices.get(i+1)-1;}
585 int prevIndex = _parent._indices.get(i);
586 int newIndex = min+_rnd.nextInt(max+1-min);
587 double rot = ((double)(newIndex-prevIndex)*Math.PI*2.0)/MAX_NUM_DIR;
588 _parent._indices.set(i, newIndex);
590 return newIndex-prevIndex;
595 public void cancelMove(int delta)
597 int i = _parent._children.indexOf(this);
598 int prevIndex = _parent._indices.get(i);
599 double rot = ((double)(-delta)*Math.PI*2.0)/MAX_NUM_DIR;
600 _parent._indices.set(i, prevIndex-delta);
604 public void rotate(double angle)
606 transform(AffineTransform.getRotateInstance(angle, _support.x, _support.y));
609 private void transform(AffineTransform a)
612 Point2D p = a.transform(_support, null);
613 _support.setLocation(p.getX(), p.getY());
614 for (int i=0;i<_children.size();i++)
616 _children.get(i).transform(a);
620 public void reflectCoordinates()
622 ArrayList<ModeleBase> mbl = _r.get_listeBases();
626 PathIterator pi = _clip.getPathIterator(AffineTransform.getRotateInstance(0.0));
627 ArrayList<Point2D.Double> p = new ArrayList<Point2D.Double>();
630 double[] args = new double[6];
631 int type= pi.currentSegment(args);
632 if ((type == PathIterator.SEG_MOVETO) || (type == PathIterator.SEG_LINETO))
635 Point2D.Double np = new Point2D.Double(args[0],args[1]);
637 System.out.println(Arrays.toString(args));
644 Point2D.Double startLeft = p.get(0);
645 Point2D.Double endLeft = p.get(1);
646 Point2D.Double endRight = p.get(2);
647 Point2D.Double startRight = p.get(3);
649 double d = startLeft.distance(endLeft);
650 double vx = endLeft.x-startLeft.x;
651 double vy = endLeft.y-startLeft.y;
652 double interval = 0.0;
657 interval = d/((double)_p._len-1);
658 System.out.println("DELTA: "+interval+" "+_r.LOOP_DISTANCE);
660 for (int n=0;n<_p._len;n++)
662 int i = _p._pos1 + n;
663 int j = _p._pos2 - n;
664 ModeleBase mbLeft = mbl.get(i);
665 mbLeft.setCoords(new Point2D.Double(startLeft.x+n*vx*interval, startLeft.y+n*vy*interval));
666 ModeleBase mbRight = mbl.get(j);
667 mbRight.setCoords(new Point2D.Double(startRight.x+n*vx*interval, startRight.y+n*vy*interval));
670 for (int i=0;i<_children.size();i++)
672 _children.get(i).reflectCoordinates();
674 if (_children.size()>0)
676 Point2D.Double center = _children.get(0)._support;
677 for (int i=0;i<_p._r.getNumPortions();i++)
679 Portion p = _p._r.getPortion(i);
680 if (p instanceof UnpairedPortion)
682 UnpairedPortion up = (UnpairedPortion) p;
683 for (int j=0;j<up._len;j++)
686 ModeleBase mbLeft = mbl.get(n);
687 mbLeft.setCoords(center);
694 placeTerminalLoop(mbl,_r);
698 private void placeTerminalLoop(ArrayList<ModeleBase> mbl, RNA r)
700 if ((_children.size()==0)&&(_p._r.getNumPortions()==1))
702 Portion p = _p._r.getPortion(0);
703 if (p instanceof UnpairedPortion)
705 UnpairedPortion up = (UnpairedPortion) p;
706 double rad = determineRadius(1,up.getNumBases(),_r);
707 int a = _p._pos1+_p._len-1;
708 int b = _p._pos2-(_p._len-1);
709 ModeleBase mbLeft = mbl.get(a);
710 ModeleBase mbRight = mbl.get(b);
711 Point2D.Double pl = mbLeft.getCoords();
712 Point2D.Double pr = mbRight.getCoords();
713 Point2D.Double pm = new Point2D.Double((pl.x+pr.x)/2.0,(pl.y+pr.y)/2.0);
714 double vx = (pl.x-pr.x)/pl.distance(pr);
715 double vy = (pl.y-pr.y)/pl.distance(pr);
716 double vnx = -vy, vny = vx;
717 Point2D.Double pc = new Point2D.Double(pm.x+rad*vnx,pm.y+rad*vny);
718 double circ = r.LOOP_DISTANCE*(1.0+up.getNumBases())+r.BASE_PAIR_DISTANCE;
719 double incrLoop = Math.PI*2.0*r.LOOP_DISTANCE/circ;
720 double angle = Math.PI*2.0*r.BASE_PAIR_DISTANCE/(2.0*circ);
721 for (int j=0;j<up._len;j++)
724 ModeleBase mb = mbl.get(n);
726 double dx = -Math.cos(angle)*vnx+Math.sin(angle)*vx;
727 double dy = -Math.cos(angle)*vny+Math.sin(angle)*vy;
728 // Point2D.Double pf = new Point2D.Double(pc.x,pc.y);
729 Point2D.Double pf = new Point2D.Double(pc.x+rad*dx,pc.y+rad*dy);
739 public String toString()
741 return "Emb.Hel.: "+_p.toString();
745 public double determineRadius(int numHelices, int numUnpaired, RNA r)
747 double circ = numHelices*r.BASE_PAIR_DISTANCE+(numHelices+numUnpaired)*r.LOOP_DISTANCE;
748 return circ/(2.0*Math.PI);
752 public void predrawTree(double x0, double y0, RNATree t, double dir, RNA r, HelixEmbedding parent, ArrayList<HelixEmbedding> all) throws Exception
758 double totCirc = r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE;
759 for (int i=0;i<t.getNumPortions();i++ )
761 Portion p = t.getPortion(i);
762 if (p instanceof PairedPortion)
764 totCirc += (r.BASE_PAIR_DISTANCE+r.LOOP_DISTANCE);
769 totCirc += r.LOOP_DISTANCE*(p.getNumBases());
770 numUBases += p.getNumBases();
773 double radius = determineRadius(numHelices+1,numUBases,r);
775 int[] placement = new int[numHelices];
776 double inc = ((double)MAX_NUM_DIR)/((double)numHelices+1);
778 for (int i=0;i<numHelices;i++ )
780 placement[i] = (int)Math.round(val);
783 double angleIncr = 2.0*Math.PI/(double)MAX_NUM_DIR;
784 x = x0+radius*Math.cos(dir+Math.PI);
785 y = y0+radius*Math.sin(dir+Math.PI);
787 for (int i=0;i<t.getNumPortions();i++ )
789 Portion p = t.getPortion(i);
790 if (p instanceof PairedPortion)
792 double ndir = dir + placement[curH]*angleIncr;
793 PairedPortion pp = (PairedPortion) p;
794 for(int j=0;j<pp._len;j++)
798 double vx = Math.cos(ndir);
799 double vy = Math.sin(ndir);
800 double nx = x+(((j)*r.LOOP_DISTANCE+radius)*vx);
801 double ny = y+(((j)*r.LOOP_DISTANCE+radius)*vy);
802 r.get_listeBases().get(i1).setCoords(new Point2D.Double(nx+r.BASE_PAIR_DISTANCE*vy/ 2.0,ny-r.BASE_PAIR_DISTANCE*vx/ 2.0));
803 r.get_listeBases().get(i2).setCoords(new Point2D.Double(nx-r.BASE_PAIR_DISTANCE*vy/ 2.0,ny+r.BASE_PAIR_DISTANCE*vx/ 2.0));
805 double nx = x+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.cos(ndir));
806 double ny = y+(((pp._len-1)*r.LOOP_DISTANCE+radius)*Math.sin(ndir));
807 HelixEmbedding nh = new HelixEmbedding(new Point2D.Double(x,y),pp,r,parent);
808 parent.addHelixEmbedding(nh,placement[curH]);
810 predrawTree(nx, ny, pp._r, ndir+Math.PI, r, nh, all);
813 else if (p instanceof UnpairedPortion)
815 UnpairedPortion up = (UnpairedPortion) p;
816 for(int j=0;j<up._len;j++)
818 r.get_listeBases().get(up._pos+j).setCoords(new Point2D.Double(x,y));
821 //System.out.println(dir);
826 public static Random _rnd = new Random();
828 private static int MAX_NUM_DIR = 8;
830 public RNATree drawRNA(double dirAngle, RNA r) {
831 RNATree t = new RNATree();
832 buildTree(0, r.get_listeBases().size() - 1, t, r );
833 System.out.println(t);
834 ArrayList<HelixEmbedding> all = new ArrayList<HelixEmbedding>();
835 HelixEmbedding root = null;
837 root = new HelixEmbedding(new Point2D.Double(0.0,0.0),new PairedPortion(0,0,0,t),r,null);
838 predrawTree(0,0,t,0.0,r,root,all);
840 double prevbadness = Double.MAX_VALUE;
841 while((steps>0)&&(prevbadness>0))
844 // Generating new structure
845 HelixEmbedding chosen = all.get(_rnd.nextInt(all.size()));
846 int delta = chosen.chooseNextMove();
850 GeneralPath p = new GeneralPath();
851 for (int i=0;i<all.size();i++)
852 { p.append(all.get(i).getShape(),false); }
854 _vp.paintImmediately(0, 0, _vp.getWidth(), _vp.getHeight());
857 //Evaluating solution
858 double badness = 0.0;
859 for (int i=0;i<all.size();i++)
861 Shape s1 = all.get(i).getShape();
862 for (int j=i+1;j<all.size();j++)
864 Shape s2 = all.get(j).getShape();
865 Area a = new Area(s1);
866 a.intersect(new Area(s2));
874 if (badness-prevbadness>0)
876 chosen.cancelMove(delta);
880 prevbadness = badness;
883 System.out.println(badness);
888 { root.reflectCoordinates(); }
889 } catch (Exception e) {
890 // TODO Auto-generated catch block