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.PhylogenyNode;
32 import org.forester.phylogeny.data.Event;
35 * Implements our algorithm for speciation - duplication inference (SDI). <p>
36 * Reference: </p> <ul> <li>Zmasek, C.M. and Eddy, S.R. (2001) "A simple
37 * algorithm to infer gene duplication and speciation events on a gene tree".
38 * Bioinformatics, in press. </ul> <p> The initialization is accomplished by:
39 * </p> <ul> <li>method "linkExtNodesOfG()" of class SDI: setting the links for
40 * the external nodes of the gene tree <li>"preorderReID(int)" from class
41 * Phylogeny: numbering of nodes of the species tree in preorder <li>the
42 * optional stripping of the species tree is accomplished by method
43 * "stripTree(Phylogeny,Phylogeny)" of class Phylogeny </ul> <p> The recursion
44 * part is accomplished by this class' method
45 * "geneTreePostOrderTraversal(PhylogenyNode)". <p> Requires JDK 1.2 or greater.
47 * @see SDI#linkNodesOfG()
49 * @see Phylogeny#preorderReID(int)
52 * PhylogenyMethods#taxonomyBasedDeletionOfExternalNodes(Phylogeny,Phylogeny)
54 * @see #geneTreePostOrderTraversal(PhylogenyNode)
56 * @author Christian M. Zmasek
58 * @version 1.102 -- last modified: 10/02/01
60 public class SDIse extends SDI {
63 * Constructor which sets the gene tree and the species tree to be compared.
64 * species_tree is the species tree to which the gene tree gene_tree will be
65 * compared to - with method "infer(boolean)". Both Trees must be completely
66 * binary and rooted. The actual inference is accomplished with method
67 * "infer(boolean)". The mapping cost L can then be calculated with method
68 * "computeMappingCost()".
70 * (Last modified: 01/11/01)
72 * @see #infer(boolean)
73 * @see SDI#computeMappingCostL()
75 * reference to a rooted binary gene Phylogeny to which assign
76 * duplication vs speciation, must have species names in the
77 * species name fields for all external nodes
79 * reference to a rooted binary species Phylogeny which might get
80 * stripped in the process, must have species names in the
81 * species name fields for all external nodes
83 public SDIse( final Phylogeny gene_tree, final Phylogeny species_tree ) {
84 super( gene_tree, species_tree );
85 _duplications_sum = 0;
86 getSpeciesTree().preOrderReId();
88 geneTreePostOrderTraversal( getGeneTree().getRoot() );
91 // Helper method for updateM( boolean, PhylogenyNode, PhylogenyNode )
92 // Calculates M for PhylogenyNode n, given that M for the two children
93 // of n has been calculated.
94 // (Last modified: 10/02/01)
95 private void calculateMforNode( final PhylogenyNode n ) {
96 if ( !n.isExternal() ) {
97 final boolean was_duplication = n.isDuplication();
98 PhylogenyNode a = n.getChildNode1().getLink(), b = n.getChildNode2().getLink();
100 if ( a.getId() > b.getId() ) {
109 if ( ( a == n.getChildNode1().getLink() ) || ( a == n.getChildNode2().getLink() ) ) {
110 event = Event.createSingleDuplicationEvent();
111 if ( !was_duplication ) {
116 event = Event.createSingleSpeciationEvent();
117 if ( was_duplication ) {
121 n.getNodeData().setEvent( event );
123 } // calculateMforNode( PhylogenyNode )
126 * Traverses the subtree of PhylogenyNode g in postorder, calculating the
127 * mapping function M, and determines which nodes represent speciation
128 * events and which ones duplication events.
130 * Preconditions: Mapping M for external nodes must have been calculated and
131 * the species tree must be labelled in preorder.
133 * (Last modified: 01/11/01)
136 * starting node of a gene tree - normally the root
138 void geneTreePostOrderTraversal( final PhylogenyNode g ) {
140 if ( !g.isExternal() ) {
141 geneTreePostOrderTraversal( g.getChildNode( 0 ) );
142 geneTreePostOrderTraversal( g.getChildNode( 1 ) );
143 a = g.getChildNode( 0 ).getLink();
144 b = g.getChildNode( 1 ).getLink();
146 if ( a.getId() > b.getId() ) {
154 // Determines whether dup. or spec.
156 if ( ( a == g.getChildNode( 0 ).getLink() ) || ( a == g.getChildNode( 1 ).getLink() ) ) {
157 event = Event.createSingleDuplicationEvent();
161 event = Event.createSingleSpeciationEvent();
163 g.getNodeData().setEvent( event );
165 } // geneTreePostOrderTraversal( PhylogenyNode )
168 * Updates the mapping function M after the root of the gene tree has been
169 * moved by one branch. It calculates M for the root of the gene tree and
170 * one of its two children.
172 * To be used ONLY by method "SDIunrooted.fastInfer(Phylogeny,Phylogeny)".
174 * (Last modfied: 10/02/01)
176 * @param prev_root_was_dup
177 * true if the previous root was a duplication, false otherwise
178 * @param prev_root_c1
179 * child 1 of the previous root
180 * @param prev_root_c2
181 * child 2 of the previous root
182 * @return number of duplications which have been assigned in gene tree
184 int updateM( final boolean prev_root_was_dup, final PhylogenyNode prev_root_c1, final PhylogenyNode prev_root_c2 ) {
185 final PhylogenyNode root = getGeneTree().getRoot();
186 if ( ( root.getChildNode1() == prev_root_c1 ) || ( root.getChildNode2() == prev_root_c1 ) ) {
187 calculateMforNode( prev_root_c1 );
190 calculateMforNode( prev_root_c2 );
193 if ( prev_root_was_dup ) {
194 event = Event.createSingleDuplicationEvent();
197 event = Event.createSingleSpeciationEvent();
199 root.getNodeData().setEvent( event );
200 calculateMforNode( root );
201 return getDuplicationsSum();
202 } // updateM( boolean, PhylogenyNode, PhylogenyNode )
203 } // End of class SDIse.