+ * Reference:
The initialization is accomplished by: + *
The recursion + * part is accomplished by this class' method + * "geneTreePostOrderTraversal(PhylogenyNode)".
Requires JDK 1.2 or greater. + * + * @see SDI#linkNodesOfG() + * + * @see Phylogeny#preorderReID(int) + * + * @see + * PhylogenyMethods#taxonomyBasedDeletionOfExternalNodes(Phylogeny,Phylogeny) + * + * @see #geneTreePostOrderTraversal(PhylogenyNode) + * + * @author Christian M. Zmasek + * + * @version 1.102 -- last modified: 10/02/01 + */ +public class SDI { final Phylogeny _gene_tree; final Phylogeny _species_tree; @@ -46,22 +75,15 @@ public abstract class SDI { /** * Constructor which sets the gene tree and the species tree to be compared. * species_tree is the species tree to which the gene tree gene_tree will be - * compared to. - * Infers for each PhylogenyNode of gene_tree whether - * it represents a speciation or duplication event by calculating and - * interpreting the mapping function M. The most parsimonious sequence of - * speciation and duplication events is assumed. - * The mapping cost L can be - * calculated with method "computeMappingCost()". + * compared to - with method "infer(boolean)". Both Trees must be completely + * binary and rooted. The actual inference is accomplished with method + * "infer(boolean)". The mapping cost L can then be calculated with method + * "computeMappingCost()". *
- * Conditions: - *
- *+ * Preconditions: Mapping M for external nodes must have been calculated and + * the species tree must be labelled in preorder. + *
+ * (Last modified: 01/11/01)
+ *
+ * @param g
+ * starting node of a gene tree - normally the root
+ */
+ void geneTreePostOrderTraversal( final PhylogenyNode g ) {
+ PhylogenyNode a, b;
+ if ( !g.isExternal() ) {
+ geneTreePostOrderTraversal( g.getChildNode( 0 ) );
+ geneTreePostOrderTraversal( g.getChildNode( 1 ) );
+ a = g.getChildNode( 0 ).getLink();
+ b = g.getChildNode( 1 ).getLink();
+ while ( a != b ) {
+ if ( a.getId() > b.getId() ) {
+ a = a.getParent();
+ }
+ else {
+ b = b.getParent();
+ }
+ }
+ g.setLink( a );
+ // Determines whether dup. or spec.
+ Event event = null;
+ if ( ( a == g.getChildNode( 0 ).getLink() ) || ( a == g.getChildNode( 1 ).getLink() ) ) {
+ event = Event.createSingleDuplicationEvent();
+ ++_duplications_sum;
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ }
+ g.getNodeData().setEvent( event );
+ }
+ } // geneTreePostOrderTraversal( PhylogenyNode )
+
/**
* Calculates the mapping function for the external nodes of the gene tree:
* links (sets the field "link" of PhylogenyNode) each external
@@ -216,14 +215,14 @@ public abstract class SDI {
* which has the same species name.
* @throws SDIException
*/
- void linkNodesOfG() throws SDIException {
+ final void linkNodesOfG() throws SDIException {
final Map
+ * To be used ONLY by method "SDIunrooted.fastInfer(Phylogeny,Phylogeny)".
+ *
+ * (Last modfied: 10/02/01)
+ *
+ * @param prev_root_was_dup
+ * true if the previous root was a duplication, false otherwise
+ * @param prev_root_c1
+ * child 1 of the previous root
+ * @param prev_root_c2
+ * child 2 of the previous root
+ * @return number of duplications which have been assigned in gene tree
+ */
+ int updateM( final boolean prev_root_was_dup, final PhylogenyNode prev_root_c1, final PhylogenyNode prev_root_c2 ) {
+ final PhylogenyNode root = getGeneTree().getRoot();
+ if ( ( root.getChildNode1() == prev_root_c1 ) || ( root.getChildNode2() == prev_root_c1 ) ) {
+ calculateMforNode( prev_root_c1 );
+ }
+ else {
+ calculateMforNode( prev_root_c2 );
+ }
+ Event event = null;
+ if ( prev_root_was_dup ) {
+ event = Event.createSingleDuplicationEvent();
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ }
+ root.getNodeData().setEvent( event );
+ calculateMforNode( root );
+ return getDuplicationsSum();
+ } // updateM( boolean, PhylogenyNode, PhylogenyNode )
+
+ // Helper method for updateM( boolean, PhylogenyNode, PhylogenyNode )
+ // Calculates M for PhylogenyNode n, given that M for the two children
+ // of n has been calculated.
+ // (Last modified: 10/02/01)
+ private void calculateMforNode( final PhylogenyNode n ) {
+ if ( !n.isExternal() ) {
+ final boolean was_duplication = n.isDuplication();
+ PhylogenyNode a = n.getChildNode1().getLink();
+ PhylogenyNode b = n.getChildNode2().getLink();
+ while ( a != b ) {
+ if ( a.getId() > b.getId() ) {
+ a = a.getParent();
+ }
+ else {
+ b = b.getParent();
+ }
+ }
+ n.setLink( a );
+ Event event = null;
+ if ( ( a == n.getChildNode1().getLink() ) || ( a == n.getChildNode2().getLink() ) ) {
+ event = Event.createSingleDuplicationEvent();
+ if ( !was_duplication ) {
+ ++_duplications_sum;
+ }
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ if ( was_duplication ) {
+ --_duplications_sum;
+ }
+ }
+ n.getNodeData().setEvent( event );
+ }
+ } // calculateMforNode( PhylogenyNode )
+
+ // Helper method for "computeMappingCost()".
+ private void computeMappingCostHelper( final PhylogenyNode g ) {
+ if ( !g.isExternal() ) {
+ computeMappingCostHelper( g.getChildNode1() );
+ computeMappingCostHelper( g.getChildNode2() );
+ if ( ( g.getLink() != g.getChildNode1().getLink() ) && ( g.getLink() != g.getChildNode2().getLink() ) ) {
+ _mapping_cost += ( ( g.getChildNode1().getLink().getId() + g.getChildNode2().getLink().getId() )
+ - ( 2 * g.getLink().getId() ) - 2 );
+ }
+ else if ( ( g.getLink() != g.getChildNode1().getLink() ) && ( g.getLink() == g.getChildNode2().getLink() ) ) {
+ _mapping_cost += ( ( g.getChildNode1().getLink().getId() - g.getLink().getId() ) + 1 );
+ }
+ else if ( ( g.getLink() == g.getChildNode1().getLink() ) && ( g.getLink() != g.getChildNode2().getLink() ) ) {
+ _mapping_cost += ( ( g.getChildNode2().getLink().getId() - g.getLink().getId() ) + 1 );
+ }
+ else {
+ _mapping_cost++;
+ }
+ }
+ }
+
+ private TaxonomyComparisonBase determineTaxonomyComparisonBase() {
+ TaxonomyComparisonBase base = null;
+ boolean all_have_id = true;
+ boolean all_have_code = true;
+ boolean all_have_sn = true;
+ for( final PhylogenyNodeIterator iter = _species_tree.iteratorExternalForward(); iter.hasNext(); ) {
+ final PhylogenyNode n = iter.next();
+ if ( n.getNodeData().isHasTaxonomy() ) {
+ final Taxonomy tax = n.getNodeData().getTaxonomy();
+ if ( ( tax.getIdentifier() == null ) || ForesterUtil.isEmpty( tax.getIdentifier().getValue() ) ) {
+ all_have_id = false;
+ }
+ if ( ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
+ all_have_code = false;
+ }
+ if ( ForesterUtil.isEmpty( tax.getScientificName() ) ) {
+ all_have_sn = false;
+ }
+ }
+ else {
+ throw new IllegalArgumentException( "species tree node [" + n + "] has no taxonomic data" );
+ }
+ }
+ for( final PhylogenyNodeIterator iter = _gene_tree.iteratorExternalForward(); iter.hasNext(); ) {
+ final PhylogenyNode n = iter.next();
+ if ( n.getNodeData().isHasTaxonomy() ) {
+ final Taxonomy tax = n.getNodeData().getTaxonomy();
+ if ( ( tax.getIdentifier() == null ) || ForesterUtil.isEmpty( tax.getIdentifier().getValue() ) ) {
+ all_have_id = false;
+ }
+ if ( ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
+ all_have_code = false;
+ }
+ if ( ForesterUtil.isEmpty( tax.getScientificName() ) ) {
+ all_have_sn = false;
+ }
+ }
+ else {
+ throw new IllegalArgumentException( "gene tree node [" + n + "] has no taxonomic data" );
+ }
+ }
+ if ( all_have_id ) {
+ base = TaxonomyComparisonBase.ID;
+ }
+ else if ( all_have_code ) {
+ base = TaxonomyComparisonBase.CODE;
+ }
+ else if ( all_have_sn ) {
+ base = TaxonomyComparisonBase.SCIENTIFIC_NAME;
+ }
+ else {
+ throw new IllegalArgumentException( "gene tree and species tree have incomparable taxonomies" );
+ }
+ return base;
+ }
+
+ /**
* Calculates the mapping function for the external nodes of the gene tree:
* links (sets the field "link" of PhylogenyNode) each external by taxonomy
* identifier
@@ -251,7 +399,7 @@ public abstract class SDI {
* which has the same species name.
* Olivier CHABROL : olivier.chabrol@univ-provence.fr
*/
- void linkNodesOfGByTaxonomyIdentifier() {
+ private final void linkNodesOfGByTaxonomyIdentifier() {
final HashMap