// Long Branch Attraction Applet // ----------------------------- // Educational demo program demonstrating the phenomenon of long branch attraction. // // Author: // Paul O. Lewis // Department of Ecology and // Evolutionary Biology // The University of Connecticut // 75 N. Eagleville Road, Unit 3043 // Storrs, CT 06269-3043 // // Tel: (860) 486-2069 // Fax: (860) 486-6364 // E-mail: paul.lewis@uconn.edu // http://hydrodictyon.eeb.uconn.edu/people/plewis/ // // Copyright (C) 1998 by Paul O. Lewis // // While now modified almost beyond recognition, this applet grew out of // playing with the Graph.java applet created by Jim Hagen and available // through the web site java.sun.com // // Permission to use, copy, modify, and distribute this software // and its documentation for NON-COMMERCIAL purposes and // without fee is hereby granted. import java.applet.Applet; import java.awt.event.*; import java.awt.*; import java.io.*; import java.util.*; import java.net.*; class TreeNode { int x; int y; int brlen; String name; String brName; TreeNode anc; int position; static final int RIGHT = 1; static final int UPRIGHT = 2; static final int UPLEFT = 3; static final int radius = 3; public TreeNode( TreeNode nd, String s, String bs, int pos ) { x = 0; y = 0; brlen = 0; anc = nd; name = new String(s); brName = new String(bs); position = pos; } public TreeNode( int init_x, int init_y ) { x = init_x; y = init_y; brlen = 0; anc = null; name = new String(""); brName = new String(""); position = 0; } public void paint( Graphics g ) { g.setColor( Color.magenta ); g.drawString( name, x + 2*radius, y ); g.setColor( Color.blue ); g.fillOval( x-radius, y-radius, 2*radius, 2*radius ); if( anc != null ) { g.drawLine( x, y, anc.x, anc.y ); // draw branch name int bnx = ( x + anc.x ) / 2; int bny = ( y + anc.y ) / 2; g.setColor( Color.red ); if( position == TreeNode.RIGHT ) g.drawString( brName, bnx + radius, bny ); else if( position == TreeNode.UPRIGHT ) g.drawString( brName, bnx + radius, bny - radius ); else if( position == TreeNode.UPLEFT ) g.drawString( brName, bnx - radius, bny - radius ); else g.drawString( brName, bnx, bny ); } } public double distanceTo( int xpos, int ypos ) { double dx = ( x - xpos ); double dy = ( y - ypos ); double d = Math.sqrt( dx*dx + dy*dy ); return d; } public void recalcBrlen() { if( anc == null ) brlen = 0; else { int xx = x - anc.x; int yy = y - anc.y; brlen = (int)( Math.sqrt( (double)( xx*xx + yy*yy ) ) ); } } }; class Tree { TreeNode root = null; TreeNode ancR = null; TreeNode ancQ = null; TreeNode tipA = null; TreeNode tipB = null; TreeNode tipC = null; TreeNode dragging = null; int width = 0; int height = 0; int ymin = 0; int ymax = 0; double paramR = 0.0; double paramQ = 0.0; double paramP = 0.0; double unit = 0.0; double sqrtTwo; public Tree( int w, int h ) { width = w; height = h; root = new TreeNode( 4*w/7, 5*h/6 ); ancR = new TreeNode( root, "", "R", TreeNode.RIGHT ); ancQ = new TreeNode( ancR, "", "Q", TreeNode.UPLEFT ); tipC = new TreeNode( ancR, "C", "P", TreeNode.UPLEFT ); tipB = new TreeNode( ancQ, "B", "Q", TreeNode.UPLEFT ); tipA = new TreeNode( ancQ, "A", "P", TreeNode.UPRIGHT ); initNodes(); // scale so that initial length of P branches // represent P = 1.0 (user will only be allowed // to shorten these branches) // double dx = ancQ.x - tipA.x; double dy = ancQ.y - tipA.y; double d = Math.sqrt( dx*dx + dy*dy ); unit = 1.0 / d; // set paramR, paramQ, and paramP now that we // have set the unit // getR(); getQ(); getP(); sqrtTwo = Math.sqrt(2.0); } void paintValue( Graphics g, int margin, String label, double value, int position ) { // first convert the double to a string with 3 decimal places int before = (int) value; double d = 1000.0 * ( value - (double)before ); d += 0.5; int after = (int)(d); String s = label + before + "." + after; FontMetrics fm = g.getFontMetrics(); int texth = fm.getHeight(); int textw = fm.stringWidth( s ); if( position == TreePanel.LEFT ) { int x = margin; int y = margin + texth; g.drawString( s, x, y ); } else if( position == TreePanel.RIGHT ) { int x = width - margin - textw; int y = margin + texth; g.drawString( s, x, y ); } else { int x = width/2 - textw/2; int y = margin + texth; g.drawString( s, x, y ); } } public void paint( Graphics g ) { root.paint(g); ancR.paint(g); ancQ.paint(g); tipA.paint(g); tipB.paint(g); tipC.paint(g); // now paint the values of P, Q, and R across the top paintValue( g, 5, "P=", paramP, TreePanel.LEFT ); paintValue( g, 5, "Q=", paramQ, TreePanel.CENTER ); paintValue( g, 5, "R=", paramR, TreePanel.RIGHT ); } public void initNodes() { ymin = height/6; ymax = 5*height/6; ancR.y = root.y - ymin; ancR.x = root.x; ancQ.y = ancR.y - ymin; ancQ.x = ancR.x - ymin; tipA.y = ancQ.y - 2*ymin; tipA.x = ancQ.x - 2*ymin; tipB.y = ancQ.y - ymin; tipB.x = ancQ.x + ymin; tipC.y = ancR.y - 2*ymin; tipC.x = ancR.x + 2*ymin; } public double getR() { double d = root.y - ancR.y; paramR = d*unit; return paramR; } public double getQ() { double dx = ancR.x - ancQ.x; double dy = ancR.y - ancQ.y; double d = Math.sqrt( dx*dx + dy*dy ); paramQ = d*unit; return paramQ; } public double getP() { double dx = ancQ.x - tipA.x; double dy = ancQ.y - tipA.y; double d = Math.sqrt( dx*dx + dy*dy ); paramP = d*unit; return paramP; } public void setDragNode( int xpos, int ypos ) { double min, d; dragging = ancR; min = ancR.distanceTo( xpos, ypos ); d = ancQ.distanceTo( xpos, ypos ); if( d < min ) { min = d; dragging = ancQ; } d = tipA.distanceTo( xpos, ypos ); if( d < min ) { min = d; dragging = tipA; } d = tipB.distanceTo( xpos, ypos ); if( d < min ) { min = d; dragging = tipB; } d = tipC.distanceTo( xpos, ypos ); if( d < min ) { min = d; dragging = tipC; } } public void clearDragNode() { dragging = null; } public int transform( double p ) { if( p <= 0.0 ) return 0; double d = p / ( unit * sqrtTwo ); int i = (int)( d + 0.5 ); return i; } public void dragEvent( int xpos, int ypos ) { if( dragging == null ) return; double p = getP(); double q = getQ(); double r = getR(); if( dragging == ancR ) { int yfloor = ymin + transform(p+q) + TreeNode.radius; int yceiling = root.y - TreeNode.radius; if( ypos > yfloor && ypos < yceiling ) { int diffy = ypos - ancR.y; int oldx = ancR.x; int oldy = ancR.y; ancR.x = root.x; ancR.y = ypos; double blen = unit * root.distanceTo( ancR.x, ancR.y ); if( blen <= 1.0 ) { // move dependent nodes accordingly ancQ.y += diffy; tipA.y += diffy; tipB.y += diffy; tipC.y += diffy; } else { ancR.x = oldx; ancR.y = oldy; } } } else if( dragging == ancQ ) { int yfloor = ymin + transform(p) + TreeNode.radius; int yceiling = ancR.y - TreeNode.radius; if( ypos > yfloor && ypos < yceiling ) { int fromAncR = ancR.y - ypos; int oldx = ancQ.x; int oldy = ancQ.y; ancQ.y = ancR.y - fromAncR; ancQ.x = ancR.x - fromAncR; double blen = unit * ancR.distanceTo( ancQ.x, ancQ.y ); if( blen <= 1.0 ) { int xoffset = ancQ.x - oldx; int yoffset = ancQ.y - oldy; // move dependent nodes accordingly tipB.y += ( 2 * yoffset ); tipA.x += xoffset; tipA.y += yoffset; } else { ancQ.x = oldx; ancQ.y = oldy; } } } else if( dragging == tipA ) { int yfloor = ymin + TreeNode.radius; int yceiling = ancQ.y - TreeNode.radius; if( ypos > yfloor && ypos < yceiling ) { int fromAncQ = ancQ.y - ypos; int oldx = tipA.x; int oldy = tipA.y; tipA.y = ancQ.y - fromAncQ; tipA.x = ancQ.x - fromAncQ; double blen = unit * ancQ.distanceTo( tipA.x, tipA.y ); if( blen <= 1.0 ) { int xoffset = tipA.x - oldx; int yoffset = tipA.y - oldy; // move dependent nodes accordingly tipC.x -= xoffset; tipC.y += yoffset; } else { tipA.x = oldx; tipA.y = oldy; } } } else if( dragging == tipB ) { int yfloor = ymin + transform(p-q) + TreeNode.radius; int yceiling = ancR.y - TreeNode.radius; if( ypos > yfloor && ypos < yceiling ) { int oldx = tipB.x; int oldy = tipB.y; tipB.x = ancR.x; tipB.y = ypos; double blen = unit * ancQ.distanceTo( tipB.x, tipB.y ); if( blen <= 1.0 ) { // move dependent nodes accordingly int offsetFromAncR = ( ancR.y - ypos ) / 2; int oldQy = ancQ.y; int oldQx = ancQ.x; ancQ.x = ancR.x - offsetFromAncR; ancQ.y = ancR.y - offsetFromAncR; int xoffset = ancQ.x - oldQx; int yoffset = ancQ.y - oldQy; tipA.x += xoffset; tipA.y += yoffset; } else { tipB.x = oldx; tipB.y = oldy; } } } else if( dragging == tipC ) { int yfloor = ymin + transform(q) + TreeNode.radius; int yceiling = ancR.y - TreeNode.radius; if( ypos > yfloor && ypos < yceiling ) { int fromAncR = ancR.y - ypos; int oldx = tipC.x; int oldy = tipC.y; tipC.y = ancR.y - fromAncR; tipC.x = ancR.x + fromAncR; double blen = unit * ancR.distanceTo( tipC.x, tipC.y ); if( blen <= 1.0 ) { int xoffset = tipC.x - oldx; int yoffset = tipC.y - oldy; // move dependent nodes accordingly tipA.x -= xoffset; tipA.y += yoffset; } else { tipC.x = oldx; tipC.y = oldy; } } } } }; class TreePanel extends Canvas implements MouseListener, MouseMotionListener { final int width = 200; final int height = 200; static final int LEFT = 1; static final int CENTER = 2; static final int RIGHT = 3; Tree tree = null; boolean greenLight = false; static final int lightDiam = 20; Font normalFont = null; Font felsensteinFont = null; Image offimg = null; Graphics offg = null; boolean first_update = true; public TreePanel() { setSize( width, height ); tree = new Tree( width, height ); } public void setOk() { greenLight = true; } public void setBad() { greenLight = false; } public void update( Graphics g ) { if( first_update ) { offimg = createImage( width, height ); offg = offimg.getGraphics(); normalFont = offg.getFont(); felsensteinFont = new Font( "Ariel", Font.BOLD, 10 ); first_update = false; } offg.setColor( Color.lightGray ); offg.fillRect( 0, 0, width, height ); if( tree != null ) tree.paint(offg); if( !greenLight ) { offg.setColor( Color.red ); offg.setFont( felsensteinFont ); FontMetrics fm = offg.getFontMetrics(); String fzs = new String("Felsenstein Zone!!"); int texth = fm.getHeight(); int textw = fm.stringWidth( fzs ); offg.drawString( fzs, width/2 - textw/2, height - texth ); offg.setFont( normalFont ); } // if( greenLight ) { // offg.setColor( Color.green ); // offg.fillOval( lightDiam, height - 2*lightDiam, lightDiam, lightDiam ); // offg.setColor( Color.lightGray ); // offg.fillOval( width - 2*lightDiam, height - 2*lightDiam, lightDiam, lightDiam ); // } // else { // offg.setColor( Color.lightGray ); // offg.fillOval( lightDiam, height - 2*lightDiam, lightDiam, lightDiam ); // offg.setColor( Color.red ); // offg.fillOval( width - 2*lightDiam, height - 2*lightDiam, lightDiam, lightDiam ); // } paint(g); } public void paint( Graphics g ) { if( first_update ) repaint(); else g.drawImage( offimg, 0, 0, this ); } public Dimension getPreferredSize() { return new Dimension( width, height ); } public void mouseMoved( MouseEvent e ) {} public void mouseEntered( MouseEvent e ) {} public void mouseExited( MouseEvent e ) {} public void mouseClicked( MouseEvent e ) {} public void mousePressed( MouseEvent e ) { int curr_x = e.getX(); int curr_y = e.getY(); tree.setDragNode( curr_x, curr_y ); } public void mouseReleased( MouseEvent e ) { int curr_x = e.getX(); int curr_y = e.getY(); tree.dragEvent( curr_x, curr_y ); tree.clearDragNode(); repaint(); } public void mouseDragged( MouseEvent e ) { int curr_x = e.getX(); int curr_y = e.getY(); tree.dragEvent( curr_x, curr_y ); repaint(); } }; class StatsPanel extends Panel { Label counts[]; Label probs[]; public StatsPanel() { counts = new Label[8]; probs = new Label[8]; // create a panel for the patterns // Panel patterns = new Panel(); patterns.setLayout( new GridLayout(9,3) ); patterns.add( new Label("A", Label.CENTER ) ); patterns.add( new Label("B", Label.CENTER ) ); patterns.add( new Label("C", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("0", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); patterns.add( new Label("1", Label.CENTER ) ); add(patterns); // create panel to display observed counts // Panel countPanel = new Panel(); countPanel.setLayout( new GridLayout(9,1) ); countPanel.add( new Label("observed", Label.CENTER ) ); countPanel.add( counts[0] = new Label("", Label.CENTER ) ); countPanel.add( counts[1] = new Label("", Label.CENTER ) ); countPanel.add( counts[2] = new Label("", Label.CENTER ) ); countPanel.add( counts[3] = new Label("", Label.CENTER ) ); countPanel.add( counts[4] = new Label("", Label.CENTER ) ); countPanel.add( counts[5] = new Label("", Label.CENTER ) ); countPanel.add( counts[6] = new Label("", Label.CENTER ) ); countPanel.add( counts[7] = new Label("", Label.CENTER ) ); add(countPanel); // create panel to display expected counts // Panel probPanel = new Panel(); probPanel.setLayout( new GridLayout(9,1) ); probPanel.add( new Label("expected", Label.CENTER ) ); probPanel.add( probs[0] = new Label("", Label.CENTER ) ); probPanel.add( probs[1] = new Label("", Label.CENTER ) ); probPanel.add( probs[2] = new Label("", Label.CENTER ) ); probPanel.add( probs[3] = new Label("", Label.CENTER ) ); probPanel.add( probs[4] = new Label("", Label.CENTER ) ); probPanel.add( probs[5] = new Label("", Label.CENTER ) ); probPanel.add( probs[6] = new Label("", Label.CENTER ) ); probPanel.add( probs[7] = new Label("", Label.CENTER ) ); add(probPanel); } public void setCount( int i, int k) { String s = "" + k; counts[i].setText(s); } public void setProb( int i, double d, int n ) { double dd = ( d * (double)n ); int k = (int)( dd + 0.5 ); probs[i].setText( String.valueOf(k) ); } }; public class LBA extends Applet implements WindowListener, ActionListener, MouseListener, MouseMotionListener { StatsPanel statsPanel = null; TreePanel treePanel = null; Button simButton = null; Choice sampleSize = null; boolean first_update = true; Random rng; double Pijk[]; double cumProb[]; int x[]; public LBA() { rng = new Random(); Pijk = new double[8]; cumProb = new double[8]; x = new int[8]; } public void setAppletFrame( Frame f ) { f.addWindowListener(this); } public void windowOpened( WindowEvent e ) {} public void windowClosing( WindowEvent e ) { System.exit(0); } public void windowClosed( WindowEvent e ) {} public void windowIconified( WindowEvent e ) {} public void windowDeiconified( WindowEvent e ) {} public void windowActivated( WindowEvent e ) {} public void windowDeactivated( WindowEvent e ) {} public void actionPerformed( ActionEvent e ) { if( e.getSource() == simButton ) { Simulate(); } } public void mouseClicked( MouseEvent e ) {} public void mousePressed( MouseEvent e ) {} public void mouseReleased( MouseEvent e ) { RecomputeProbs(); } public void mouseEntered( MouseEvent e ) {} public void mouseExited( MouseEvent e ) {} public void mouseDragged( MouseEvent e ) {} public void mouseMoved( MouseEvent e ) {} public int RecomputeProbs() { String ss = sampleSize.getSelectedItem(); int n = Integer.valueOf(ss).intValue(); double Rprob = treePanel.tree.getR(); double Qprob = treePanel.tree.getQ(); double Pprob = treePanel.tree.getP(); double oneMinusR = 1.0 - Rprob; double oneMinusQ = 1.0 - Qprob; double oneMinusP = 1.0 - Pprob; Pijk[0] = oneMinusR * oneMinusP * oneMinusP * oneMinusQ * oneMinusQ; Pijk[1] = oneMinusR * Pprob * oneMinusP * oneMinusQ * oneMinusQ; Pijk[2] = oneMinusR * oneMinusP * oneMinusP * Qprob * oneMinusQ; Pijk[3] = oneMinusR * Pprob * oneMinusP * oneMinusQ * oneMinusQ; Pijk[4] = oneMinusR * Pprob * oneMinusP * Qprob * oneMinusQ; Pijk[5] = oneMinusR * Pprob * Pprob * oneMinusQ * oneMinusQ; Pijk[6] = oneMinusR * oneMinusP * Qprob * ( 1.0 + Pprob * oneMinusQ ); Pijk[7] = Rprob + ( oneMinusR * Pprob * Qprob * ( 1.0 + Pprob * oneMinusQ ) ); if( Pijk[6] > Pijk[5] && Pijk[6] > Pijk[4] ) treePanel.setOk(); else treePanel.setBad(); statsPanel.setProb( 0, Pijk[0], n ); statsPanel.setProb( 1, Pijk[1], n ); statsPanel.setProb( 2, Pijk[2], n ); statsPanel.setProb( 3, Pijk[3], n ); statsPanel.setProb( 4, Pijk[4], n ); statsPanel.setProb( 5, Pijk[5], n ); statsPanel.setProb( 6, Pijk[6], n ); statsPanel.setProb( 7, Pijk[7], n ); return n; } public void Simulate() { int n = RecomputeProbs(); cumProb[0] = Pijk[0]; cumProb[1] = cumProb[0] + Pijk[1]; cumProb[2] = cumProb[1] + Pijk[2]; cumProb[3] = cumProb[2] + Pijk[3]; cumProb[4] = cumProb[3] + Pijk[4]; cumProb[5] = cumProb[4] + Pijk[5]; cumProb[6] = cumProb[5] + Pijk[6]; cumProb[7] = cumProb[6] + Pijk[7]; x[0] = 0; x[1] = 0; x[2] = 0; x[3] = 0; x[4] = 0; x[5] = 0; x[6] = 0; x[7] = 0; for( int i = 0; i < n; i++ ) { double rnd = rng.nextDouble(); if( rnd < cumProb[0] ) x[0] += 1; else if( rnd < cumProb[1] ) x[1] += 1; else if( rnd < cumProb[2] ) x[2] += 1; else if( rnd < cumProb[3] ) x[3] += 1; else if( rnd < cumProb[4] ) x[4] += 1; else if( rnd < cumProb[5] ) x[5] += 1; else if( rnd < cumProb[6] ) x[6] += 1; else x[7] += 1; } statsPanel.setCount( 0, x[0] ); statsPanel.setCount( 1, x[1] ); statsPanel.setCount( 2, x[2] ); statsPanel.setCount( 3, x[3] ); statsPanel.setCount( 4, x[4] ); statsPanel.setCount( 5, x[5] ); statsPanel.setCount( 6, x[6] ); statsPanel.setCount( 7, x[7] ); } public void init() { setLayout( new BorderLayout() ); Panel p = new Panel(); statsPanel = new StatsPanel(); p.add(statsPanel); treePanel = new TreePanel(); treePanel.addMouseListener(this); treePanel.addMouseListener(treePanel); treePanel.addMouseMotionListener(this); treePanel.addMouseMotionListener(treePanel); p.add(treePanel); add( "Center", p ); Panel pp = new Panel(); simButton = new Button( "Simulate" ); simButton.addActionListener(this); pp.add(simButton); sampleSize = new Choice(); sampleSize.addItem( "100" ); sampleSize.addItem( "1000" ); sampleSize.addItem( "10000" ); pp.add( new Label( "Sample size:", Label.RIGHT ) ); pp.add( sampleSize ); add( "South", pp ); repaint(); } public static void main( String args[] ) { Frame f = new Frame("Long Branch Attraction Demo"); f.setSize( 500, 300 ); LBA lba = new LBA(); lba.setAppletFrame(f); lba.init(); f.add( "Center", lba ); f.show(); } }