2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2008-2009 Christian M. Zmasek
6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
7 // Copyright (C) 2000-2001 Washington University School of Medicine
8 // and Howard Hughes Medical Institute
11 // This library is free software; you can redistribute it and/or
12 // modify it under the terms of the GNU Lesser General Public
13 // License as published by the Free Software Foundation; either
14 // version 2.1 of the License, or (at your option) any later version.
16 // This library is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 // Lesser General Public License for more details.
21 // You should have received a copy of the GNU Lesser General Public
22 // License along with this library; if not, write to the Free Software
23 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 // Contact: phylosoft @ gmail . com
26 // WWW: www.phylosoft.org/forester
28 package org.forester.sdi;
30 import org.forester.phylogeny.Phylogeny;
31 import org.forester.phylogeny.PhylogenyMethods;
32 import org.forester.phylogeny.PhylogenyNode;
33 import org.forester.phylogeny.data.Event;
36 * Implements our algorithm for speciation - duplication inference (SDI). <p>
37 * Reference: </p> <ul> <li>Zmasek, C.M. and Eddy, S.R. (2001) "A simple
38 * algorithm to infer gene duplication and speciation events on a gene tree".
39 * Bioinformatics, in press. </ul> <p> The initialization is accomplished by:
40 * </p> <ul> <li>method "linkExtNodesOfG()" of class SDI: setting the links for
41 * the external nodes of the gene tree <li>"preorderReID(int)" from class
42 * Phylogeny: numbering of nodes of the species tree in preorder <li>the
43 * optional stripping of the species tree is accomplished by method
44 * "stripTree(Phylogeny,Phylogeny)" of class Phylogeny </ul> <p> The recursion
45 * part is accomplished by this class' method
46 * "geneTreePostOrderTraversal(PhylogenyNode)". <p> Requires JDK 1.2 or greater.
48 * @see SDI#linkNodesOfG()
50 * @see Phylogeny#preorderReID(int)
53 * PhylogenyMethods#taxonomyBasedDeletionOfExternalNodes(Phylogeny,Phylogeny)
55 * @see #geneTreePostOrderTraversal(PhylogenyNode)
57 * @author Christian M. Zmasek
59 * @version 1.102 -- last modified: 10/02/01
61 public class SDIse extends SDI {
64 * Constructor which sets the gene tree and the species tree to be compared.
65 * species_tree is the species tree to which the gene tree gene_tree will be
66 * compared to - with method "infer(boolean)". Both Trees must be completely
67 * binary and rooted. The actual inference is accomplished with method
68 * "infer(boolean)". The mapping cost L can then be calculated with method
69 * "computeMappingCost()".
71 * (Last modified: 01/11/01)
73 * @see #infer(boolean)
74 * @see SDI#computeMappingCostL()
76 * reference to a rooted binary gene Phylogeny to which assign
77 * duplication vs speciation, must have species names in the
78 * species name fields for all external nodes
80 * reference to a rooted binary species Phylogeny which might get
81 * stripped in the process, must have species names in the
82 * species name fields for all external nodes
83 * @throws SDIException
85 public SDIse( final Phylogeny gene_tree, final Phylogeny species_tree ) throws SDIException {
86 super( gene_tree, species_tree );
87 _duplications_sum = 0;
88 PhylogenyMethods.preOrderReId( getSpeciesTree() );
90 geneTreePostOrderTraversal( getGeneTree().getRoot() );
93 // Helper method for updateM( boolean, PhylogenyNode, PhylogenyNode )
94 // Calculates M for PhylogenyNode n, given that M for the two children
95 // of n has been calculated.
96 // (Last modified: 10/02/01)
97 private void calculateMforNode( final PhylogenyNode n ) {
98 if ( !n.isExternal() ) {
99 final boolean was_duplication = n.isDuplication();
100 PhylogenyNode a = n.getChildNode1().getLink();
101 PhylogenyNode b = n.getChildNode2().getLink();
103 if ( a.getId() > b.getId() ) {
112 if ( ( a == n.getChildNode1().getLink() ) || ( a == n.getChildNode2().getLink() ) ) {
113 event = Event.createSingleDuplicationEvent();
114 if ( !was_duplication ) {
119 event = Event.createSingleSpeciationEvent();
120 if ( was_duplication ) {
124 n.getNodeData().setEvent( event );
126 } // calculateMforNode( PhylogenyNode )
129 * Traverses the subtree of PhylogenyNode g in postorder, calculating the
130 * mapping function M, and determines which nodes represent speciation
131 * events and which ones duplication events.
133 * Preconditions: Mapping M for external nodes must have been calculated and
134 * the species tree must be labelled in preorder.
136 * (Last modified: 01/11/01)
139 * starting node of a gene tree - normally the root
141 void geneTreePostOrderTraversal( final PhylogenyNode g ) {
143 if ( !g.isExternal() ) {
144 geneTreePostOrderTraversal( g.getChildNode( 0 ) );
145 geneTreePostOrderTraversal( g.getChildNode( 1 ) );
146 a = g.getChildNode( 0 ).getLink();
147 b = g.getChildNode( 1 ).getLink();
149 if ( a.getId() > b.getId() ) {
157 // Determines whether dup. or spec.
159 if ( ( a == g.getChildNode( 0 ).getLink() ) || ( a == g.getChildNode( 1 ).getLink() ) ) {
160 event = Event.createSingleDuplicationEvent();
164 event = Event.createSingleSpeciationEvent();
166 g.getNodeData().setEvent( event );
168 } // geneTreePostOrderTraversal( PhylogenyNode )
171 * Updates the mapping function M after the root of the gene tree has been
172 * moved by one branch. It calculates M for the root of the gene tree and
173 * one of its two children.
175 * To be used ONLY by method "SDIunrooted.fastInfer(Phylogeny,Phylogeny)".
177 * (Last modfied: 10/02/01)
179 * @param prev_root_was_dup
180 * true if the previous root was a duplication, false otherwise
181 * @param prev_root_c1
182 * child 1 of the previous root
183 * @param prev_root_c2
184 * child 2 of the previous root
185 * @return number of duplications which have been assigned in gene tree
187 int updateM( final boolean prev_root_was_dup, final PhylogenyNode prev_root_c1, final PhylogenyNode prev_root_c2 ) {
188 final PhylogenyNode root = getGeneTree().getRoot();
189 if ( ( root.getChildNode1() == prev_root_c1 ) || ( root.getChildNode2() == prev_root_c1 ) ) {
190 calculateMforNode( prev_root_c1 );
193 calculateMforNode( prev_root_c2 );
196 if ( prev_root_was_dup ) {
197 event = Event.createSingleDuplicationEvent();
200 event = Event.createSingleSpeciationEvent();
202 root.getNodeData().setEvent( event );
203 calculateMforNode( root );
204 return getDuplicationsSum();
205 } // updateM( boolean, PhylogenyNode, PhylogenyNode )
206 } // End of class SDIse.