forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java

   1 // $Id:
   2 // $
   3 //
   4 // FORESTER -- software libraries and applications
   5 // for evolutionary biology research and applications.
   6 //
   7 // Copyright (C) 2008-2009 Christian M. Zmasek
   8 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   9 // All rights reserved
  10 //
  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.
  15 //
  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.
  20 //
  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
  24 //
  25 // Contact: phylosoft @ gmail . com
  26 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
  27
  28 package org.forester.evoinference;
  29
  30 import java.io.File;
  31 import java.io.FileInputStream;
  32 import java.io.StringWriter;
  33 import java.util.Date;
  34 import java.util.List;
  35
  36 import org.forester.evoinference.distance.NeighborJoining;
  37 import org.forester.evoinference.distance.NeighborJoiningX;
  38 import org.forester.evoinference.distance.PairwiseDistanceCalculator;
  39 import org.forester.evoinference.matrix.character.BasicCharacterStateMatrix;
  40 import org.forester.evoinference.matrix.character.CharacterStateMatrix;
  41 import org.forester.evoinference.matrix.character.CharacterStateMatrix.BinaryStates;
  42 import org.forester.evoinference.matrix.character.CharacterStateMatrix.GainLossStates;
  43 import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix;
  44 import org.forester.evoinference.matrix.distance.DistanceMatrix;
  45 import org.forester.evoinference.parsimony.DolloParsimony;
  46 import org.forester.evoinference.parsimony.FitchParsimony;
  47 import org.forester.io.parsers.GeneralMsaParser;
  48 import org.forester.io.parsers.SymmetricalDistanceMatrixParser;
  49 import org.forester.io.parsers.nhx.NHXParser;
  50 import org.forester.msa.Msa;
  51 import org.forester.phylogeny.Phylogeny;
  52 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  53 import org.forester.phylogeny.factories.PhylogenyFactory;
  54 import org.forester.util.ForesterUtil;
  55
  56 public class TestPhylogenyReconstruction {
  57
  58     private final static double ZERO_DIFF = 1.0E-9;
  59
  60     public static boolean isEqual( final double a, final double b ) {
  61         return ( ( Math.abs( a - b ) ) < ZERO_DIFF );
  62     }
  63
  64     public static boolean isUnequal( final double a, final double b ) {
  65         return !isEqual( a, b );
  66     }
  67
  68     public static void main( final String[] args ) {
  69         if ( testNeighborJoining() ) {
  70             System.out.println( "OK." );
  71         }
  72         else {
  73             System.out.println( "failed." );
  74         }
  75         timeNeighborJoining();
  76     }
  77
  78     public static boolean test( final File test_dir ) {
  79         System.out.print( "  Basic symmetrical distance matrix: " );
  80         if ( !testBasicSymmetricalDistanceMatrix() ) {
  81             System.out.println( "failed." );
  82             return false;
  83         }
  84         System.out.println( "OK." );
  85         System.out.print( "  Basic character state matrix: " );
  86         if ( !testBasicCharacterStateMatrix() ) {
  87             System.out.println( "failed." );
  88             return false;
  89         }
  90         System.out.println( "OK." );
  91         System.out.print( "  Symmetrical distance matrix parser: " );
  92         if ( !testSymmetricalDistanceMatrixParser() ) {
  93             System.out.println( "failed." );
  94             return false;
  95         }
  96         System.out.println( "OK." );
  97         System.out.print( "  Distance Calculation: " );
  98         if ( !testDistanceCalculationMethods( test_dir ) ) {
  99             System.out.println( "failed." );
 100             return false;
 101         }
 102         System.out.println( "OK." );
 103         System.out.print( "  Neighbor Joining: " );
 104         if ( !testNeighborJoining() ) {
 105             System.out.println( "failed." );
 106             return false;
 107         }
 108         System.out.println( "OK." );
 109         System.out.print( "  Dollo Parsimony: " );
 110         if ( !testDolloParsimony() ) {
 111             System.out.println( "failed." );
 112             return false;
 113         }
 114         System.out.println( "OK." );
 115         System.out.print( "  Dollo Parsimony on non binary trees: " );
 116         if ( !testDolloParsimonyOnNonBinaryTree() ) {
 117             System.out.println( "failed." );
 118             return false;
 119         }
 120         System.out.println( "OK." );
 121         System.out.print( "  Fitch Parsimony: " );
 122         if ( !testFitchParsimony() ) {
 123             System.out.println( "failed." );
 124             return false;
 125         }
 126         System.out.println( "OK." );
 127         return true;
 128     }
 129
 130     private static boolean testDistanceCalculationMethods( final File test_dir ) {
 131         try {
 132             final Msa msa0 = GeneralMsaParser.parse( new FileInputStream( test_dir + ForesterUtil.FILE_SEPARATOR
 133                     + "bcl.aln" ) );
 134             final BasicSymmetricalDistanceMatrix pwd0 = PairwiseDistanceCalculator.calcKimuraDistances( msa0 );
 135             if ( pwd0.getSize() != 120 ) {
 136                 return false;
 137             }
 138             for( int i = 0; i < pwd0.getSize(); ++i ) {
 139                 if ( !isEqual( pwd0.getValue( i, i ), 0.0 ) ) {
 140                     return false;
 141                 }
 142             }
 143         }
 144         catch ( final Exception e ) {
 145             e.printStackTrace( System.out );
 146             return false;
 147         }
 148         return true;
 149     }
 150
 151     private static boolean testBasicCharacterStateMatrix() {
 152         try {
 153             final CharacterStateMatrix<String> matrix_0 = new BasicCharacterStateMatrix<String>( 4, 8 );
 154             final CharacterStateMatrix<String> matrix_00 = new BasicCharacterStateMatrix<String>( 4, 8 );
 155             matrix_0.setIdentifier( 0, "A" );
 156             matrix_0.setIdentifier( 1, "B" );
 157             matrix_0.setIdentifier( 2, "C" );
 158             matrix_0.setIdentifier( 3, "D" );
 159             matrix_0.setCharacter( 0, "0" );
 160             matrix_0.setCharacter( 1, "1" );
 161             matrix_0.setCharacter( 2, "2" );
 162             matrix_0.setCharacter( 3, "3" );
 163             matrix_0.setCharacter( 4, "4" );
 164             matrix_0.setCharacter( 5, "5" );
 165             matrix_0.setCharacter( 6, "6" );
 166             matrix_0.setCharacter( 7, "7" );
 167             matrix_00.setIdentifier( 0, "A" );
 168             matrix_00.setIdentifier( 1, "B" );
 169             matrix_00.setIdentifier( 2, "C" );
 170             matrix_00.setIdentifier( 3, "D" );
 171             matrix_00.setCharacter( 3, "3" );
 172             matrix_00.setCharacter( 4, "4" );
 173             if ( !matrix_0.getCharacter( 1 ).equals( "1" ) ) {
 174                 return false;
 175             }
 176             if ( !matrix_0.getIdentifier( 0 ).equals( "A" ) ) {
 177                 return false;
 178             }
 179             matrix_0.setState( 0, 0, "00" );
 180             matrix_00.setState( 0, 0, "00" );
 181             if ( !matrix_0.getState( 0, 0 ).equals( "00" ) ) {
 182                 return false;
 183             }
 184             matrix_0.setState( 0, 1, "01" );
 185             matrix_00.setState( 0, 1, "01" );
 186             if ( !matrix_0.getState( 0, 1 ).equals( "01" ) ) {
 187                 return false;
 188             }
 189             matrix_0.setState( 1, 1, "11" );
 190             matrix_00.setState( 1, 1, "11" );
 191             if ( !matrix_0.getState( 1, 1 ).equals( "11" ) ) {
 192                 return false;
 193             }
 194             matrix_0.setState( 1, 0, "10" );
 195             matrix_00.setState( 1, 0, "10" );
 196             if ( !matrix_0.getState( 1, 0 ).equals( "10" ) ) {
 197                 return false;
 198             }
 199             matrix_0.setState( 1, 2, "12" );
 200             matrix_00.setState( 1, 2, "12" );
 201             if ( !matrix_0.getState( 1, 2 ).equals( "12" ) ) {
 202                 return false;
 203             }
 204             matrix_0.setState( 3, 7, "37" );
 205             matrix_00.setState( 3, 7, "37" );
 206             if ( !matrix_0.getState( 3, 7 ).equals( "37" ) ) {
 207                 return false;
 208             }
 209             matrix_0.setState( 2, 6, "26" );
 210             matrix_00.setState( 2, 6, "26" );
 211             if ( !matrix_0.getState( 2, 6 ).equals( "26" ) ) {
 212                 return false;
 213             }
 214             matrix_0.setState( "D", "3", "33" );
 215             matrix_00.setState( "D", "3", "33" );
 216             if ( !matrix_0.getState( 3, 3 ).equals( "33" ) ) {
 217                 return false;
 218             }
 219             if ( !matrix_0.getState( "D", "3" ).equals( "33" ) ) {
 220                 return false;
 221             }
 222             matrix_0.setState( "C", "4", "24" );
 223             matrix_00.setState( "C", "4", "24" );
 224             if ( !matrix_0.getState( 2, 4 ).equals( "24" ) ) {
 225                 return false;
 226             }
 227             if ( !matrix_0.getState( "C", "4" ).equals( "24" ) ) {
 228                 return false;
 229             }
 230             if ( matrix_0.isEmpty() ) {
 231                 return false;
 232             }
 233             if ( matrix_0.getNumberOfIdentifiers() != 4 ) {
 234                 return false;
 235             }
 236             if ( matrix_0.getNumberOfCharacters() != 8 ) {
 237                 return false;
 238             }
 239             if ( !matrix_0.equals( matrix_0 ) ) {
 240                 return false;
 241             }
 242             if ( !matrix_0.equals( matrix_00 ) ) {
 243                 return false;
 244             }
 245             matrix_00.setState( "C", "4", "123" );
 246             if ( matrix_0.equals( matrix_00 ) ) {
 247                 return false;
 248             }
 249             final Integer[][] ints = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 250             final CharacterStateMatrix<Integer> matrix_000 = new BasicCharacterStateMatrix<Integer>( ints );
 251             matrix_000.toString();
 252             if ( matrix_000.getNumberOfCharacters() != 4 ) {
 253                 return false;
 254             }
 255             if ( matrix_000.getNumberOfIdentifiers() != 3 ) {
 256                 return false;
 257             }
 258             if ( matrix_000.getState( 0, 1 ) != 2 ) {
 259                 return false;
 260             }
 261             if ( matrix_000.getState( 2, 3 ) != 12 ) {
 262                 return false;
 263             }
 264             final Integer[][] ints0 = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 265             final CharacterStateMatrix<Integer> matrix_0000 = new BasicCharacterStateMatrix<Integer>( ints0 );
 266             if ( !matrix_000.equals( matrix_0000 ) ) {
 267                 return false;
 268             }
 269             final Integer[][] ints00 = { { 1, 2, 3, -4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 270             final CharacterStateMatrix<Integer> matrix_00000 = new BasicCharacterStateMatrix<Integer>( ints00 );
 271             if ( matrix_000.equals( matrix_00000 ) ) {
 272                 return false;
 273             }
 274             final CharacterStateMatrix<String> clone0 = matrix_0.copy();
 275             final CharacterStateMatrix<String> clone00 = matrix_00.copy();
 276             if ( !clone0.equals( matrix_0 ) ) {
 277                 return false;
 278             }
 279             if ( !clone00.equals( matrix_00 ) ) {
 280                 return false;
 281             }
 282             if ( clone00.equals( clone0 ) ) {
 283                 return false;
 284             }
 285             final CharacterStateMatrix<String> pivot0 = matrix_0.pivot();
 286             final CharacterStateMatrix<String> pivot00 = matrix_00.pivot();
 287             if ( !pivot0.getState( 1, 0 ).equals( "01" ) ) {
 288                 return false;
 289             }
 290             if ( !pivot0.getState( 6, 2 ).equals( "26" ) ) {
 291                 return false;
 292             }
 293             if ( !matrix_0.getState( 2, 6 ).equals( "26" ) ) {
 294                 return false;
 295             }
 296             final CharacterStateMatrix<String> pivotpivot00 = pivot00.pivot();
 297             if ( !pivotpivot00.equals( matrix_00 ) ) {
 298                 return false;
 299             }
 300             final CharacterStateMatrix<BinaryStates> nex = new BasicCharacterStateMatrix<BinaryStates>( 4, 3 );
 301             nex.setIdentifier( 0, "amphioxus" );
 302             nex.setIdentifier( 1, "sponge" );
 303             nex.setIdentifier( 2, "sea_anemone" );
 304             nex.setIdentifier( 3, "cobra" );
 305             nex.setCharacter( 0, "notch" );
 306             nex.setCharacter( 1, "homeobox" );
 307             nex.setCharacter( 2, "wnt" );
 308             nex.setState( 0, 0, BinaryStates.ABSENT );
 309             nex.setState( 0, 1, BinaryStates.ABSENT );
 310             nex.setState( 0, 2, BinaryStates.ABSENT );
 311             nex.setState( 1, 0, BinaryStates.PRESENT );
 312             nex.setState( 1, 1, BinaryStates.PRESENT );
 313             nex.setState( 1, 2, BinaryStates.ABSENT );
 314             nex.setState( 2, 0, BinaryStates.PRESENT );
 315             nex.setState( 2, 1, BinaryStates.PRESENT );
 316             nex.setState( 2, 2, BinaryStates.PRESENT );
 317             nex.setState( 3, 0, BinaryStates.PRESENT );
 318             nex.setState( 3, 1, BinaryStates.ABSENT );
 319             nex.setState( 3, 2, BinaryStates.ABSENT );
 320             StringWriter w = new StringWriter();
 321             nex.toWriter( w, CharacterStateMatrix.Format.NEXUS_BINARY );
 322             //System.out.println( w.getBuffer().toString() );
 323             w = new StringWriter();
 324             nex.pivot().toWriter( w, CharacterStateMatrix.Format.NEXUS_BINARY );
 325             //System.out.println( w.getBuffer().toString() );
 326         }
 327         catch ( final Exception e ) {
 328             e.printStackTrace( System.out );
 329             return false;
 330         }
 331         return true;
 332     }
 333
 334     private static boolean testBasicSymmetricalDistanceMatrix() {
 335         try {
 336             final DistanceMatrix matrix_0 = new BasicSymmetricalDistanceMatrix( 4 );
 337             matrix_0.setIdentifier( 0, "A" );
 338             matrix_0.setIdentifier( 1, "B" );
 339             matrix_0.setIdentifier( 2, "C" );
 340             matrix_0.setIdentifier( 3, "0123456789012" );
 341             matrix_0.setValue( 1, 0, 0.00001 );
 342             matrix_0.setValue( 0, 2, 0.0000009 );
 343             matrix_0.setValue( 3, 0, 3.0 );
 344             matrix_0.setValue( 1, 2, 4.0 );
 345             matrix_0.setValue( 3, 1, 5.0 );
 346             matrix_0.setValue( 2, 3, 6.0 );
 347             if ( !matrix_0.getIdentifier( 0 ).equals( "A" ) ) {
 348                 return false;
 349             }
 350             if ( !matrix_0.getIdentifier( 1 ).equals( "B" ) ) {
 351                 return false;
 352             }
 353             if ( !matrix_0.getIdentifier( 2 ).equals( "C" ) ) {
 354                 return false;
 355             }
 356             if ( !matrix_0.getIdentifier( 3 ).equals( "0123456789012" ) ) {
 357                 return false;
 358             }
 359             if ( matrix_0.getSize() != 4 ) {
 360                 return false;
 361             }
 362             if ( !isEqual( matrix_0.getValue( 0, 0 ), 0.0 ) ) {
 363                 return false;
 364             }
 365             if ( !isEqual( matrix_0.getValue( 3, 3 ), 0.0 ) ) {
 366                 return false;
 367             }
 368             if ( !isEqual( matrix_0.getValue( 0, 1 ), 0.00001 ) ) {
 369                 return false;
 370             }
 371             if ( !isEqual( matrix_0.getValue( 0, 2 ), 0.0000009 ) ) {
 372                 return false;
 373             }
 374             if ( !isEqual( matrix_0.getValue( 0, 3 ), 3 ) ) {
 375                 return false;
 376             }
 377             if ( !isEqual( matrix_0.getValue( 1, 0 ), 0.00001 ) ) {
 378                 return false;
 379             }
 380             if ( !isEqual( matrix_0.getValue( 1, 2 ), 4 ) ) {
 381                 return false;
 382             }
 383             if ( !isEqual( matrix_0.getValue( 1, 3 ), 5 ) ) {
 384                 return false;
 385             }
 386             if ( !isEqual( matrix_0.getValue( 2, 0 ), 0.0000009 ) ) {
 387                 return false;
 388             }
 389             if ( !isEqual( matrix_0.getValue( 2, 1 ), 4 ) ) {
 390                 return false;
 391             }
 392             if ( !isEqual( matrix_0.getValue( 2, 3 ), 6 ) ) {
 393                 return false;
 394             }
 395             if ( !isEqual( matrix_0.getValue( 3, 0 ), 3 ) ) {
 396                 return false;
 397             }
 398             if ( !isEqual( matrix_0.getValue( 3, 1 ), 5 ) ) {
 399                 return false;
 400             }
 401             if ( !isEqual( matrix_0.getValue( 3, 2 ), 6 ) ) {
 402                 return false;
 403             }
 404             final StringBuffer matrix_0_phylip = new StringBuffer();
 405             matrix_0_phylip.append( "    4" );
 406             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 407             matrix_0_phylip.append( "A           0.000000  0.000010  0.000001  3.000000" );
 408             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 409             matrix_0_phylip.append( "B           0.000010  0.000000  4.000000  5.000000" );
 410             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 411             matrix_0_phylip.append( "C           0.000001  4.000000  0.000000  6.000000" );
 412             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 413             matrix_0_phylip.append( "0123456789  3.000000  5.000000  6.000000  0.000000" );
 414             if ( !matrix_0_phylip.toString()
 415                     .equals( matrix_0.toStringBuffer( DistanceMatrix.Format.PHYLIP ).toString() ) ) {
 416                 return false;
 417             }
 418         }
 419         catch ( final Exception e ) {
 420             e.printStackTrace( System.out );
 421             return false;
 422         }
 423         return true;
 424     }
 425
 426     private static boolean testDolloParsimony() {
 427         try {
 428             final BinaryStates PRESENT = BinaryStates.PRESENT;
 429             final BinaryStates ABSENT = BinaryStates.ABSENT;
 430             final GainLossStates UNCHANGED_PRESENT = GainLossStates.UNCHANGED_PRESENT;
 431             final DolloParsimony dollo1 = DolloParsimony.createInstance();
 432             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
 433             final String p1_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 434             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
 435             CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9,
 436                                                                                                                                            1 );
 437             m1.setIdentifier( 0, "a" );
 438             m1.setIdentifier( 1, "b" );
 439             m1.setIdentifier( 2, "c" );
 440             m1.setIdentifier( 3, "d" );
 441             m1.setIdentifier( 4, "e" );
 442             m1.setIdentifier( 5, "f" );
 443             m1.setIdentifier( 6, "g" );
 444             m1.setIdentifier( 7, "h" );
 445             m1.setIdentifier( 8, "i" );
 446             m1.setCharacter( 0, "0" );
 447             m1.setState( "a", "0", PRESENT );
 448             m1.setState( "b", "0", ABSENT );
 449             m1.setState( "c", "0", PRESENT );
 450             m1.setState( "d", "0", ABSENT );
 451             m1.setState( "e", "0", ABSENT );
 452             m1.setState( "f", "0", ABSENT );
 453             m1.setState( "g", "0", ABSENT );
 454             m1.setState( "h", "0", ABSENT );
 455             m1.setState( "i", "0", ABSENT );
 456             dollo1.execute( p1, m1 );
 457             if ( dollo1.getTotalGains() != 1 ) {
 458                 return false;
 459             }
 460             if ( dollo1.getTotalLosses() != 1 ) {
 461                 return false;
 462             }
 463             if ( dollo1.getTotalUnchanged() != 15 ) {
 464                 return false;
 465             }
 466             m1.setState( "b", "0", PRESENT );
 467             dollo1.execute( p1, m1 );
 468             if ( dollo1.getTotalGains() != 1 ) {
 469                 return false;
 470             }
 471             if ( dollo1.getTotalLosses() != 0 ) {
 472                 return false;
 473             }
 474             if ( dollo1.getTotalUnchanged() != 16 ) {
 475                 return false;
 476             }
 477             m1.setState( "b", "0", ABSENT );
 478             m1.setState( "e", "0", PRESENT );
 479             dollo1.execute( p1, m1 );
 480             if ( dollo1.getTotalGains() != 1 ) {
 481                 return false;
 482             }
 483             if ( dollo1.getTotalLosses() != 3 ) {
 484                 return false;
 485             }
 486             if ( dollo1.getTotalUnchanged() != 13 ) {
 487                 return false;
 488             }
 489             m1.setState( "a", "0", ABSENT );
 490             m1.setState( "c", "0", ABSENT );
 491             m1.setState( "g", "0", PRESENT );
 492             dollo1.setReturnInternalStates( true );
 493             dollo1.setReturnGainLossMatrix( true );
 494             dollo1.execute( p1, m1 );
 495             if ( dollo1.getTotalGains() != 1 ) {
 496                 return false;
 497             }
 498             if ( dollo1.getTotalLosses() != 3 ) {
 499                 return false;
 500             }
 501             if ( dollo1.getTotalUnchanged() != 13 ) {
 502                 return false;
 503             }
 504             final DolloParsimony dollo2 = DolloParsimony.createInstance();
 505             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
 506             final String p2_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h,i)gi)ai,((j,k,l)jl,(m,n,o)mo,(p,q,r)pr)jr)root";
 507             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
 508             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m2 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 18,
 509                                                                                                                                                  4 );
 510             m2.setIdentifier( 0, "a" );
 511             m2.setIdentifier( 1, "b" );
 512             m2.setIdentifier( 2, "c" );
 513             m2.setIdentifier( 3, "d" );
 514             m2.setIdentifier( 4, "e" );
 515             m2.setIdentifier( 5, "f" );
 516             m2.setIdentifier( 6, "g" );
 517             m2.setIdentifier( 7, "h" );
 518             m2.setIdentifier( 8, "i" );
 519             m2.setIdentifier( 9, "j" );
 520             m2.setIdentifier( 10, "k" );
 521             m2.setIdentifier( 11, "l" );
 522             m2.setIdentifier( 12, "m" );
 523             m2.setIdentifier( 13, "n" );
 524             m2.setIdentifier( 14, "o" );
 525             m2.setIdentifier( 15, "p" );
 526             m2.setIdentifier( 16, "q" );
 527             m2.setIdentifier( 17, "r" );
 528             m2.setCharacter( 0, "0" );
 529             m2.setCharacter( 1, "1" );
 530             m2.setCharacter( 2, "2" );
 531             m2.setCharacter( 3, "3" );
 532             m2.setState( "a", "0", PRESENT );
 533             m2.setState( "b", "0", ABSENT );
 534             m2.setState( "c", "0", PRESENT );
 535             m2.setState( "d", "0", ABSENT );
 536             m2.setState( "e", "0", ABSENT );
 537             m2.setState( "f", "0", ABSENT );
 538             m2.setState( "g", "0", ABSENT );
 539             m2.setState( "h", "0", ABSENT );
 540             m2.setState( "i", "0", ABSENT );
 541             m2.setState( "j", "0", ABSENT );
 542             m2.setState( "k", "0", ABSENT );
 543             m2.setState( "l", "0", ABSENT );
 544             m2.setState( "m", "0", ABSENT );
 545             m2.setState( "n", "0", ABSENT );
 546             m2.setState( "o", "0", ABSENT );
 547             m2.setState( "p", "0", ABSENT );
 548             m2.setState( "q", "0", ABSENT );
 549             m2.setState( "r", "0", ABSENT );
 550             m2.setState( "a", "1", PRESENT );
 551             m2.setState( "b", "1", ABSENT );
 552             m2.setState( "c", "1", PRESENT );
 553             m2.setState( "d", "1", ABSENT );
 554             m2.setState( "e", "1", ABSENT );
 555             m2.setState( "f", "1", ABSENT );
 556             m2.setState( "g", "1", PRESENT );
 557             m2.setState( "h", "1", ABSENT );
 558             m2.setState( "i", "1", ABSENT );
 559             m2.setState( "j", "1", PRESENT );
 560             m2.setState( "k", "1", ABSENT );
 561             m2.setState( "l", "1", ABSENT );
 562             m2.setState( "m", "1", PRESENT );
 563             m2.setState( "n", "1", ABSENT );
 564             m2.setState( "o", "1", ABSENT );
 565             m2.setState( "p", "1", ABSENT );
 566             m2.setState( "q", "1", ABSENT );
 567             m2.setState( "r", "1", ABSENT );
 568             m2.setState( "a", "2", ABSENT );
 569             m2.setState( "b", "2", ABSENT );
 570             m2.setState( "c", "2", ABSENT );
 571             m2.setState( "d", "2", ABSENT );
 572             m2.setState( "e", "2", ABSENT );
 573             m2.setState( "f", "2", ABSENT );
 574             m2.setState( "g", "2", ABSENT );
 575             m2.setState( "h", "2", ABSENT );
 576             m2.setState( "i", "2", ABSENT );
 577             m2.setState( "j", "2", PRESENT );
 578             m2.setState( "k", "2", ABSENT );
 579             m2.setState( "l", "2", ABSENT );
 580             m2.setState( "m", "2", PRESENT );
 581             m2.setState( "n", "2", ABSENT );
 582             m2.setState( "o", "2", ABSENT );
 583             m2.setState( "p", "2", PRESENT );
 584             m2.setState( "q", "2", ABSENT );
 585             m2.setState( "r", "2", ABSENT );
 586             m2.setState( "a", "3", ABSENT );
 587             m2.setState( "b", "3", ABSENT );
 588             m2.setState( "c", "3", PRESENT );
 589             m2.setState( "d", "3", ABSENT );
 590             m2.setState( "e", "3", ABSENT );
 591             m2.setState( "f", "3", ABSENT );
 592             m2.setState( "g", "3", PRESENT );
 593             m2.setState( "h", "3", ABSENT );
 594             m2.setState( "i", "3", ABSENT );
 595             m2.setState( "j", "3", ABSENT );
 596             m2.setState( "k", "3", ABSENT );
 597             m2.setState( "l", "3", ABSENT );
 598             m2.setState( "m", "3", ABSENT );
 599             m2.setState( "n", "3", ABSENT );
 600             m2.setState( "o", "3", ABSENT );
 601             m2.setState( "p", "3", ABSENT );
 602             m2.setState( "q", "3", ABSENT );
 603             m2.setState( "r", "3", ABSENT );
 604             dollo2.setReturnInternalStates( true );
 605             dollo2.setReturnGainLossMatrix( true );
 606             dollo2.execute( p2, m2 );
 607             final CharacterStateMatrix<BinaryStates> i_m = dollo2.getInternalStatesMatrix();
 608             final CharacterStateMatrix<GainLossStates> gl_m = dollo2.getGainLossMatrix();
 609             if ( dollo2.getTotalGains() != 3 ) {
 610                 return false;
 611             }
 612             if ( dollo2.getTotalLosses() != 22 ) {
 613                 return false;
 614             }
 615             if ( dollo2.getTotalUnchanged() != 95 ) {
 616                 return false;
 617             }
 618             if ( i_m.getState( "ab", "0" ) != PRESENT ) {
 619                 return false;
 620             }
 621             if ( i_m.getState( "ac", "0" ) != PRESENT ) {
 622                 return false;
 623             }
 624             if ( i_m.getState( "ad", "0" ) != ABSENT ) {
 625                 return false;
 626             }
 627             if ( i_m.getState( "af", "0" ) != ABSENT ) {
 628                 return false;
 629             }
 630             if ( i_m.getState( "ef", "0" ) != ABSENT ) {
 631                 return false;
 632             }
 633             if ( i_m.getState( "ai", "0" ) != ABSENT ) {
 634                 return false;
 635             }
 636             if ( i_m.getState( "gi", "0" ) != ABSENT ) {
 637                 return false;
 638             }
 639             if ( i_m.getState( "jl", "0" ) != ABSENT ) {
 640                 return false;
 641             }
 642             if ( i_m.getState( "mo", "0" ) != ABSENT ) {
 643                 return false;
 644             }
 645             if ( i_m.getState( "pr", "0" ) != ABSENT ) {
 646                 return false;
 647             }
 648             if ( i_m.getState( "jr", "0" ) != ABSENT ) {
 649                 return false;
 650             }
 651             if ( i_m.getState( "root", "0" ) != ABSENT ) {
 652                 return false;
 653             }
 654             if ( i_m.getState( "ab", "1" ) != PRESENT ) {
 655                 return false;
 656             }
 657             if ( i_m.getState( "ac", "1" ) != PRESENT ) {
 658                 return false;
 659             }
 660             if ( i_m.getState( "ad", "1" ) != PRESENT ) {
 661                 return false;
 662             }
 663             if ( i_m.getState( "af", "1" ) != PRESENT ) {
 664                 return false;
 665             }
 666             if ( i_m.getState( "ef", "1" ) != ABSENT ) {
 667                 return false;
 668             }
 669             if ( i_m.getState( "ai", "1" ) != PRESENT ) {
 670                 return false;
 671             }
 672             if ( i_m.getState( "gi", "1" ) != PRESENT ) {
 673                 return false;
 674             }
 675             if ( i_m.getState( "jl", "1" ) != PRESENT ) {
 676                 return false;
 677             }
 678             if ( i_m.getState( "mo", "1" ) != PRESENT ) {
 679                 return false;
 680             }
 681             if ( i_m.getState( "pr", "1" ) != ABSENT ) {
 682                 return false;
 683             }
 684             if ( i_m.getState( "jr", "1" ) != PRESENT ) {
 685                 return false;
 686             }
 687             if ( i_m.getState( "root", "1" ) != PRESENT ) {
 688                 return false;
 689             }
 690             if ( i_m.getState( "ab", "2" ) != ABSENT ) {
 691                 return false;
 692             }
 693             if ( i_m.getState( "ac", "2" ) != ABSENT ) {
 694                 return false;
 695             }
 696             if ( i_m.getState( "ad", "2" ) != ABSENT ) {
 697                 return false;
 698             }
 699             if ( i_m.getState( "af", "2" ) != ABSENT ) {
 700                 return false;
 701             }
 702             if ( i_m.getState( "ef", "2" ) != ABSENT ) {
 703                 return false;
 704             }
 705             if ( i_m.getState( "ai", "2" ) != ABSENT ) {
 706                 return false;
 707             }
 708             if ( i_m.getState( "gi", "2" ) != ABSENT ) {
 709                 return false;
 710             }
 711             if ( i_m.getState( "jl", "2" ) != PRESENT ) {
 712                 return false;
 713             }
 714             if ( i_m.getState( "mo", "2" ) != PRESENT ) {
 715                 return false;
 716             }
 717             if ( i_m.getState( "pr", "2" ) != PRESENT ) {
 718                 return false;
 719             }
 720             if ( i_m.getState( "jr", "2" ) != PRESENT ) {
 721                 return false;
 722             }
 723             if ( i_m.getState( "root", "2" ) != ABSENT ) {
 724                 return false;
 725             }
 726             if ( i_m.getState( "ab", "3" ) != ABSENT ) {
 727                 return false;
 728             }
 729             if ( i_m.getState( "ac", "3" ) != PRESENT ) {
 730                 return false;
 731             }
 732             if ( i_m.getState( "ad", "3" ) != PRESENT ) {
 733                 return false;
 734             }
 735             if ( i_m.getState( "af", "3" ) != PRESENT ) {
 736                 return false;
 737             }
 738             if ( i_m.getState( "ef", "3" ) != ABSENT ) {
 739                 return false;
 740             }
 741             if ( i_m.getState( "ai", "3" ) != PRESENT ) {
 742                 return false;
 743             }
 744             if ( i_m.getState( "gi", "3" ) != PRESENT ) {
 745                 return false;
 746             }
 747             if ( i_m.getState( "jl", "3" ) != ABSENT ) {
 748                 return false;
 749             }
 750             if ( i_m.getState( "mo", "3" ) != ABSENT ) {
 751                 return false;
 752             }
 753             if ( i_m.getState( "pr", "3" ) != ABSENT ) {
 754                 return false;
 755             }
 756             if ( i_m.getState( "jr", "3" ) != ABSENT ) {
 757                 return false;
 758             }
 759             if ( i_m.getState( "root", "3" ) != ABSENT ) {
 760                 return false;
 761             }
 762             if ( gl_m.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
 763                 return false;
 764             }
 765             final DolloParsimony dollo9 = DolloParsimony.createInstance();
 766             final PhylogenyFactory factory9 = ParserBasedPhylogenyFactory.getInstance();
 767             final String p9_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 768             final Phylogeny p9 = factory9.create( p9_str, new NHXParser() )[ 0 ];
 769             m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9, 3 );
 770             m1.setIdentifier( 0, "a" );
 771             m1.setIdentifier( 1, "b" );
 772             m1.setIdentifier( 2, "c" );
 773             m1.setIdentifier( 3, "d" );
 774             m1.setIdentifier( 4, "e" );
 775             m1.setIdentifier( 5, "f" );
 776             m1.setIdentifier( 6, "g" );
 777             m1.setIdentifier( 7, "h" );
 778             m1.setIdentifier( 8, "i" );
 779             m1.setState( 0, 0, PRESENT );
 780             m1.setState( 1, 0, ABSENT );
 781             m1.setState( 2, 0, PRESENT );
 782             m1.setState( 3, 0, ABSENT );
 783             m1.setState( 4, 0, ABSENT );
 784             m1.setState( 5, 0, ABSENT );
 785             m1.setState( 6, 0, ABSENT );
 786             m1.setState( 7, 0, ABSENT );
 787             m1.setState( 8, 0, ABSENT );
 788             m1.setState( 0, 1, PRESENT );
 789             m1.setState( 1, 1, PRESENT );
 790             m1.setState( 2, 1, PRESENT );
 791             m1.setState( 3, 1, PRESENT );
 792             m1.setState( 4, 1, ABSENT );
 793             m1.setState( 5, 1, ABSENT );
 794             m1.setState( 6, 1, ABSENT );
 795             m1.setState( 7, 1, ABSENT );
 796             m1.setState( 8, 1, ABSENT );
 797             m1.setState( 0, 2, PRESENT );
 798             m1.setState( 1, 2, ABSENT );
 799             m1.setState( 2, 2, ABSENT );
 800             m1.setState( 3, 2, ABSENT );
 801             m1.setState( 4, 2, ABSENT );
 802             m1.setState( 5, 2, ABSENT );
 803             m1.setState( 6, 2, ABSENT );
 804             m1.setState( 7, 2, PRESENT );
 805             m1.setState( 8, 2, ABSENT );
 806             dollo9.execute( p9, m1 );
 807             if ( dollo9.getTotalGains() != 3 ) {
 808                 return false;
 809             }
 810             if ( dollo9.getTotalLosses() != 6 ) {
 811                 return false;
 812             }
 813             final DolloParsimony dollo10 = DolloParsimony.createInstance();
 814             final PhylogenyFactory factory10 = ParserBasedPhylogenyFactory.getInstance();
 815             final String p10_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 816             final Phylogeny p10 = factory10.create( p10_str, new NHXParser() )[ 0 ];
 817             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m10 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9,
 818                                                                                                                                                   1 );
 819             m10.setIdentifier( 0, "a" );
 820             m10.setIdentifier( 1, "b" );
 821             m10.setIdentifier( 2, "c" );
 822             m10.setIdentifier( 3, "d" );
 823             m10.setIdentifier( 4, "e" );
 824             m10.setIdentifier( 5, "f" );
 825             m10.setIdentifier( 6, "g" );
 826             m10.setIdentifier( 7, "h" );
 827             m10.setIdentifier( 8, "i" );
 828             m10.setState( 0, 0, PRESENT );
 829             m10.setState( 1, 0, ABSENT );
 830             m10.setState( 2, 0, PRESENT );
 831             m10.setState( 3, 0, ABSENT );
 832             m10.setState( 4, 0, ABSENT );
 833             m10.setState( 5, 0, ABSENT );
 834             m10.setState( 6, 0, ABSENT );
 835             m10.setState( 7, 0, ABSENT );
 836             m10.setState( 8, 0, ABSENT );
 837             dollo10.execute( p10, m10 );
 838             if ( dollo10.getTotalGains() != 1 ) {
 839                 return false;
 840             }
 841             if ( dollo10.getTotalLosses() != 1 ) {
 842                 return false;
 843             }
 844         }
 845         catch ( final Exception e ) {
 846             e.printStackTrace( System.out );
 847             return false;
 848         }
 849         return true;
 850     }
 851
 852     private static boolean testDolloParsimonyOnNonBinaryTree() {
 853         try {
 854             final BinaryStates PRESENT = BinaryStates.PRESENT;
 855             final BinaryStates ABSENT = BinaryStates.ABSENT;
 856             final DolloParsimony dollo1 = DolloParsimony.createInstance();
 857             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
 858             final String p1_str = "((((((a,b,y)aby,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 859             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
 860             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 10,
 861                                                                                                                                                  1 );
 862             m1.setIdentifier( 0, "a" );
 863             m1.setIdentifier( 1, "b" );
 864             m1.setIdentifier( 2, "y" );
 865             m1.setIdentifier( 3, "c" );
 866             m1.setIdentifier( 4, "d" );
 867             m1.setIdentifier( 5, "e" );
 868             m1.setIdentifier( 6, "f" );
 869             m1.setIdentifier( 7, "g" );
 870             m1.setIdentifier( 8, "h" );
 871             m1.setIdentifier( 9, "i" );
 872             m1.setCharacter( 0, "0" );
 873             m1.setState( "a", "0", PRESENT );
 874             m1.setState( "b", "0", ABSENT );
 875             m1.setState( "y", "0", PRESENT );
 876             m1.setState( "c", "0", PRESENT );
 877             m1.setState( "d", "0", ABSENT );
 878             m1.setState( "e", "0", ABSENT );
 879             m1.setState( "f", "0", ABSENT );
 880             m1.setState( "g", "0", ABSENT );
 881             m1.setState( "h", "0", ABSENT );
 882             m1.setState( "i", "0", ABSENT );
 883             dollo1.execute( p1, m1 );
 884             if ( dollo1.getTotalGains() != 1 ) {
 885                 return false;
 886             }
 887             if ( dollo1.getTotalLosses() != 1 ) {
 888                 return false;
 889             }
 890             if ( dollo1.getTotalUnchanged() != 16 ) {
 891                 return false;
 892             }
 893             m1.setState( "b", "0", PRESENT );
 894             dollo1.execute( p1, m1 );
 895             if ( dollo1.getTotalGains() != 1 ) {
 896                 return false;
 897             }
 898             if ( dollo1.getTotalLosses() != 0 ) {
 899                 return false;
 900             }
 901             if ( dollo1.getTotalUnchanged() != 17 ) {
 902                 return false;
 903             }
 904             m1.setState( "a", "0", ABSENT );
 905             m1.setState( "b", "0", ABSENT );
 906             dollo1.execute( p1, m1 );
 907             if ( dollo1.getTotalGains() != 1 ) {
 908                 return false;
 909             }
 910             if ( dollo1.getTotalLosses() != 2 ) {
 911                 return false;
 912             }
 913             if ( dollo1.getTotalUnchanged() != 15 ) {
 914                 return false;
 915             }
 916             m1.setState( "y", "0", ABSENT );
 917             dollo1.execute( p1, m1 );
 918             if ( dollo1.getTotalGains() != 1 ) {
 919                 return false;
 920             }
 921             if ( dollo1.getTotalLosses() != 0 ) {
 922                 return false;
 923             }
 924             if ( dollo1.getTotalUnchanged() != 17 ) {
 925                 return false;
 926             }
 927             final DolloParsimony dollo2 = DolloParsimony.createInstance();
 928             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
 929             final String p2_str = "((((((a,b,y)aby,c,d)cad,e,f)af,(g,h)gh)ah,i))r";
 930             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
 931             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m2 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 10,
 932                                                                                                                                                  1 );
 933             m2.setIdentifier( 0, "a" );
 934             m2.setIdentifier( 1, "b" );
 935             m2.setIdentifier( 2, "y" );
 936             m2.setIdentifier( 3, "c" );
 937             m2.setIdentifier( 4, "d" );
 938             m2.setIdentifier( 5, "e" );
 939             m2.setIdentifier( 6, "f" );
 940             m2.setIdentifier( 7, "g" );
 941             m2.setIdentifier( 8, "h" );
 942             m2.setIdentifier( 9, "i" );
 943             m2.setCharacter( 0, "0" );
 944             m2.setState( "a", "0", PRESENT );
 945             m2.setState( "b", "0", ABSENT );
 946             m2.setState( "y", "0", PRESENT );
 947             m2.setState( "c", "0", PRESENT );
 948             m2.setState( "d", "0", ABSENT );
 949             m2.setState( "e", "0", ABSENT );
 950             m2.setState( "f", "0", ABSENT );
 951             m2.setState( "g", "0", ABSENT );
 952             m2.setState( "h", "0", ABSENT );
 953             m2.setState( "i", "0", ABSENT );
 954             dollo2.setReturnInternalStates( true );
 955             dollo2.execute( p2, m2 );
 956             CharacterStateMatrix<BinaryStates> i_m2 = dollo2.getInternalStatesMatrix();
 957             if ( i_m2.getState( "aby", "0" ) != PRESENT ) {
 958                 return false;
 959             }
 960             if ( i_m2.getState( "cad", "0" ) != PRESENT ) {
 961                 return false;
 962             }
 963             if ( i_m2.getState( "af", "0" ) != ABSENT ) {
 964                 return false;
 965             }
 966             if ( i_m2.getState( "gh", "0" ) != ABSENT ) {
 967                 return false;
 968             }
 969             if ( i_m2.getState( "ah", "0" ) != ABSENT ) {
 970                 return false;
 971             }
 972             if ( i_m2.getState( "r", "0" ) != ABSENT ) {
 973                 return false;
 974             }
 975             if ( dollo2.getTotalGains() != 1 ) {
 976                 return false;
 977             }
 978             if ( dollo2.getTotalLosses() != 2 ) {
 979                 return false;
 980             }
 981             if ( dollo2.getTotalUnchanged() != 14 ) {
 982                 return false;
 983             }
 984             m2.setState( "b", "0", PRESENT );
 985             dollo2.execute( p2, m2 );
 986             if ( dollo2.getTotalGains() != 1 ) {
 987                 return false;
 988             }
 989             if ( dollo2.getTotalLosses() != 1 ) {
 990                 return false;
 991             }
 992             if ( dollo2.getTotalUnchanged() != 15 ) {
 993                 return false;
 994             }
 995             m2.setState( "a", "0", ABSENT );
 996             m2.setState( "b", "0", ABSENT );
 997             dollo2.execute( p2, m2 );
 998             if ( dollo2.getTotalGains() != 1 ) {
 999                 return false;
1000             }
1001             if ( dollo2.getTotalLosses() != 3 ) {
1002                 return false;
1003             }
1004             if ( dollo2.getTotalUnchanged() != 13 ) {
1005                 return false;
1006             }
1007             m2.setState( "y", "0", ABSENT );
1008             dollo2.execute( p2, m2 );
1009             if ( dollo2.getTotalGains() != 1 ) {
1010                 return false;
1011             }
1012             if ( dollo2.getTotalLosses() != 0 ) {
1013                 return false;
1014             }
1015             if ( dollo2.getTotalUnchanged() != 16 ) {
1016                 return false;
1017             }
1018             m2.setState( "c", "0", ABSENT );
1019             dollo2.execute( p2, m2 );
1020             if ( dollo2.getTotalGains() != 0 ) {
1021                 return false;
1022             }
1023             if ( dollo2.getTotalLosses() != 0 ) {
1024                 return false;
1025             }
1026             if ( dollo2.getTotalUnchanged() != 17 ) {
1027                 return false;
1028             }
1029             m2.setState( "y", "0", PRESENT );
1030             m2.setState( "e", "0", PRESENT );
1031             dollo2.execute( p2, m2 );
1032             if ( dollo2.getTotalGains() != 1 ) {
1033                 return false;
1034             }
1035             if ( dollo2.getTotalLosses() != 5 ) {
1036                 return false;
1037             }
1038             if ( dollo2.getTotalUnchanged() != 11 ) {
1039                 return false;
1040             }
1041             i_m2 = dollo2.getInternalStatesMatrix();
1042             if ( i_m2.getState( "aby", "0" ) != PRESENT ) {
1043                 return false;
1044             }
1045             if ( i_m2.getState( "cad", "0" ) != PRESENT ) {
1046                 return false;
1047             }
1048             if ( i_m2.getState( "af", "0" ) != PRESENT ) {
1049                 return false;
1050             }
1051             if ( i_m2.getState( "gh", "0" ) != ABSENT ) {
1052                 return false;
1053             }
1054             if ( i_m2.getState( "ah", "0" ) != ABSENT ) {
1055                 return false;
1056             }
1057             if ( i_m2.getState( "r", "0" ) != ABSENT ) {
1058                 return false;
1059             }
1060         }
1061         catch ( final Exception e ) {
1062             e.printStackTrace( System.out );
1063             return false;
1064         }
1065         return true;
1066     }
1067
1068     private static boolean testFitchParsimony() {
1069         try {
1070             final BinaryStates PRESENT = BinaryStates.PRESENT;
1071             final BinaryStates ABSENT = BinaryStates.ABSENT;
1072             final GainLossStates GAIN = GainLossStates.GAIN;
1073             final GainLossStates LOSS = GainLossStates.LOSS;
1074             final GainLossStates UNCHANGED_PRESENT = GainLossStates.UNCHANGED_PRESENT;
1075             final GainLossStates UNCHANGED_ABSENT = GainLossStates.UNCHANGED_ABSENT;
1076             final FitchParsimony<String> fitch1 = new FitchParsimony<String>();
1077             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
1078             final String p1_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h,i)gi)ai,((j,k,l)jl,(m,n,o)mo,(p,q,r)pr)jr)root";
1079             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
1080             final CharacterStateMatrix<String> m1 = new BasicCharacterStateMatrix<String>( 18, 1 );
1081             m1.setIdentifier( 0, "a" );
1082             m1.setIdentifier( 1, "b" );
1083             m1.setIdentifier( 2, "c" );
1084             m1.setIdentifier( 3, "d" );
1085             m1.setIdentifier( 4, "e" );
1086             m1.setIdentifier( 5, "f" );
1087             m1.setIdentifier( 6, "g" );
1088             m1.setIdentifier( 7, "h" );
1089             m1.setIdentifier( 8, "i" );
1090             m1.setIdentifier( 9, "j" );
1091             m1.setIdentifier( 10, "k" );
1092             m1.setIdentifier( 11, "l" );
1093             m1.setIdentifier( 12, "m" );
1094             m1.setIdentifier( 13, "n" );
1095             m1.setIdentifier( 14, "o" );
1096             m1.setIdentifier( 15, "p" );
1097             m1.setIdentifier( 16, "q" );
1098             m1.setIdentifier( 17, "r" );
1099             m1.setCharacter( 0, "0" );
1100             m1.setState( "a", "0", "A" );
1101             m1.setState( "b", "0", "A" );
1102             m1.setState( "c", "0", "B" );
1103             m1.setState( "d", "0", "C" );
1104             m1.setState( "e", "0", "D" );
1105             m1.setState( "f", "0", "A" );
1106             m1.setState( "g", "0", "A" );
1107             m1.setState( "h", "0", "B" );
1108             m1.setState( "i", "0", "C" );
1109             m1.setState( "j", "0", "A" );
1110             m1.setState( "k", "0", "B" );
1111             m1.setState( "l", "0", "C" );
1112             m1.setState( "m", "0", "B" );
1113             m1.setState( "n", "0", "B" );
1114             m1.setState( "o", "0", "B" );
1115             m1.setState( "p", "0", "A" );
1116             m1.setState( "q", "0", "C" );
1117             m1.setState( "r", "0", "D" );
1118             fitch1.setReturnInternalStates( true );
1119             fitch1.setReturnGainLossMatrix( false );
1120             fitch1.setRandomize( false );
1121             fitch1.execute( p1, m1 );
1122             final CharacterStateMatrix<String> i_m = fitch1.getInternalStatesMatrix();
1123             final CharacterStateMatrix<List<String>> i_m_all = fitch1.getInternalStatesMatrixPriorToTraceback();
1124             if ( fitch1.getCost() != 10 ) {
1125                 return false;
1126             }
1127             if ( !i_m.getState( "ab", "0" ).equals( "A" ) ) {
1128                 return false;
1129             }
1130             if ( !i_m.getState( "ac", "0" ).equals( "A" ) ) {
1131                 return false;
1132             }
1133             if ( !i_m.getState( "ad", "0" ).equals( "A" ) ) {
1134                 return false;
1135             }
1136             if ( !i_m.getState( "ef", "0" ).equals( "A" ) ) {
1137                 return false;
1138             }
1139             if ( !i_m.getState( "ai", "0" ).equals( "A" ) ) {
1140                 return false;
1141             }
1142             if ( !i_m.getState( "gi", "0" ).equals( "A" ) ) {
1143                 return false;
1144             }
1145             if ( !i_m.getState( "jl", "0" ).equals( "A" ) ) {
1146                 return false;
1147             }
1148             if ( !i_m.getState( "mo", "0" ).equals( "B" ) ) {
1149                 return false;
1150             }
1151             if ( !i_m.getState( "pr", "0" ).equals( "A" ) ) {
1152                 return false;
1153             }
1154             if ( i_m_all.getState( "ab", "0" ).size() != 1 ) {
1155                 return false;
1156             }
1157             if ( !i_m_all.getState( "ab", "0" ).contains( "A" ) ) {
1158                 return false;
1159             }
1160             if ( i_m_all.getState( "ac", "0" ).size() != 2 ) {
1161                 return false;
1162             }
1163             if ( !i_m_all.getState( "ac", "0" ).contains( "A" ) ) {
1164                 return false;
1165             }
1166             if ( !i_m_all.getState( "ac", "0" ).contains( "B" ) ) {
1167                 return false;
1168             }
1169             if ( i_m_all.getState( "ad", "0" ).size() != 3 ) {
1170                 return false;
1171             }
1172             if ( !i_m_all.getState( "ad", "0" ).contains( "A" ) ) {
1173                 return false;
1174             }
1175             if ( !i_m_all.getState( "ad", "0" ).contains( "B" ) ) {
1176                 return false;
1177             }
1178             if ( !i_m_all.getState( "ad", "0" ).contains( "C" ) ) {
1179                 return false;
1180             }
1181             if ( i_m_all.getState( "af", "0" ).size() != 1 ) {
1182                 return false;
1183             }
1184             if ( !i_m_all.getState( "af", "0" ).contains( "A" ) ) {
1185                 return false;
1186             }
1187             if ( i_m_all.getState( "ef", "0" ).size() != 2 ) {
1188                 return false;
1189             }
1190             if ( !i_m_all.getState( "ef", "0" ).contains( "A" ) ) {
1191                 return false;
1192             }
1193             if ( !i_m_all.getState( "ef", "0" ).contains( "D" ) ) {
1194                 return false;
1195             }
1196             if ( i_m_all.getState( "gi", "0" ).size() != 3 ) {
1197                 return false;
1198             }
1199             if ( !i_m_all.getState( "gi", "0" ).contains( "A" ) ) {
1200                 return false;
1201             }
1202             if ( !i_m_all.getState( "gi", "0" ).contains( "B" ) ) {
1203                 return false;
1204             }
1205             if ( !i_m_all.getState( "gi", "0" ).contains( "C" ) ) {
1206                 return false;
1207             }
1208             if ( i_m_all.getState( "ai", "0" ).size() != 1 ) {
1209                 return false;
1210             }
1211             if ( !i_m_all.getState( "ai", "0" ).contains( "A" ) ) {
1212                 return false;
1213             }
1214             if ( i_m_all.getState( "jl", "0" ).size() != 3 ) {
1215                 return false;
1216             }
1217             if ( !i_m_all.getState( "jl", "0" ).contains( "A" ) ) {
1218                 return false;
1219             }
1220             if ( !i_m_all.getState( "jl", "0" ).contains( "B" ) ) {
1221                 return false;
1222             }
1223             if ( !i_m_all.getState( "jl", "0" ).contains( "C" ) ) {
1224                 return false;
1225             }
1226             if ( i_m_all.getState( "mo", "0" ).size() != 1 ) {
1227                 return false;
1228             }
1229             if ( !i_m_all.getState( "mo", "0" ).contains( "B" ) ) {
1230                 return false;
1231             }
1232             if ( i_m_all.getState( "pr", "0" ).size() != 3 ) {
1233                 return false;
1234             }
1235             if ( !i_m_all.getState( "pr", "0" ).contains( "A" ) ) {
1236                 return false;
1237             }
1238             if ( !i_m_all.getState( "pr", "0" ).contains( "C" ) ) {
1239                 return false;
1240             }
1241             if ( !i_m_all.getState( "pr", "0" ).contains( "D" ) ) {
1242                 return false;
1243             }
1244             if ( i_m_all.getState( "jr", "0" ).size() != 4 ) {
1245                 return false;
1246             }
1247             if ( !i_m_all.getState( "jr", "0" ).contains( "A" ) ) {
1248                 return false;
1249             }
1250             if ( !i_m_all.getState( "jr", "0" ).contains( "B" ) ) {
1251                 return false;
1252             }
1253             if ( !i_m_all.getState( "jr", "0" ).contains( "C" ) ) {
1254                 return false;
1255             }
1256             if ( !i_m_all.getState( "jr", "0" ).contains( "D" ) ) {
1257                 return false;
1258             }
1259             final FitchParsimony<String> fitch2 = new FitchParsimony<String>();
1260             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
1261             final String p2_str = "((a,b)ab,(c,(d,e)de)cde)r";
1262             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
1263             final CharacterStateMatrix<String> m2 = new BasicCharacterStateMatrix<String>( 5, 1 );
1264             m2.setIdentifier( 0, "a" );
1265             m2.setIdentifier( 1, "b" );
1266             m2.setIdentifier( 2, "c" );
1267             m2.setIdentifier( 3, "d" );
1268             m2.setIdentifier( 4, "e" );
1269             m2.setCharacter( 0, "0" );
1270             m2.setState( "a", "0", "C" );
1271             m2.setState( "b", "0", "A" );
1272             m2.setState( "c", "0", "C" );
1273             m2.setState( "d", "0", "A" );
1274             m2.setState( "e", "0", "G" );
1275             fitch2.setReturnInternalStates( true );
1276             fitch2.setReturnGainLossMatrix( false );
1277             fitch2.execute( p2, m2 );
1278             final CharacterStateMatrix<String> i_m2 = fitch2.getInternalStatesMatrix();
1279             final CharacterStateMatrix<List<String>> i_m_all2 = fitch2.getInternalStatesMatrixPriorToTraceback();
1280             if ( fitch2.getCost() != 3 ) {
1281                 return false;
1282             }
1283             if ( !i_m2.getState( "ab", "0" ).equals( "A" ) ) {
1284                 return false;
1285             }
1286             if ( !i_m2.getState( "de", "0" ).equals( "A" ) ) {
1287                 return false;
1288             }
1289             if ( !i_m2.getState( "cde", "0" ).equals( "A" ) ) {
1290                 return false;
1291             }
1292             if ( !i_m2.getState( "r", "0" ).equals( "A" ) ) {
1293                 return false;
1294             }
1295             if ( i_m_all2.getState( "cde", "0" ).size() != 3 ) {
1296                 return false;
1297             }
1298             if ( !i_m_all2.getState( "cde", "0" ).contains( "A" ) ) {
1299                 return false;
1300             }
1301             if ( !i_m_all2.getState( "cde", "0" ).contains( "C" ) ) {
1302                 return false;
1303             }
1304             if ( !i_m_all2.getState( "cde", "0" ).contains( "G" ) ) {
1305                 return false;
1306             }
1307             if ( i_m_all2.getState( "ab", "0" ).size() != 2 ) {
1308                 return false;
1309             }
1310             if ( !i_m_all2.getState( "ab", "0" ).contains( "A" ) ) {
1311                 return false;
1312             }
1313             if ( !i_m_all2.getState( "ab", "0" ).contains( "C" ) ) {
1314                 return false;
1315             }
1316             fitch2.setReturnInternalStates( true );
1317             fitch2.setReturnGainLossMatrix( false );
1318             fitch2.setUseLast( true );
1319             fitch2.execute( p2, m2 );
1320             final CharacterStateMatrix<String> i_m21 = fitch2.getInternalStatesMatrix();
1321             final CharacterStateMatrix<List<String>> i_m_all21 = fitch2.getInternalStatesMatrixPriorToTraceback();
1322             if ( fitch2.getCost() != 3 ) {
1323                 return false;
1324             }
1325             if ( !i_m21.getState( "ab", "0" ).equals( "C" ) ) {
1326                 return false;
1327             }
1328             if ( !i_m21.getState( "de", "0" ).equals( "G" ) ) {
1329                 return false;
1330             }
1331             if ( !i_m21.getState( "cde", "0" ).equals( "C" ) ) {
1332                 return false;
1333             }
1334             if ( !i_m21.getState( "r", "0" ).equals( "C" ) ) {
1335                 return false;
1336             }
1337             if ( i_m_all21.getState( "cde", "0" ).size() != 3 ) {
1338                 return false;
1339             }
1340             if ( !i_m_all21.getState( "cde", "0" ).contains( "A" ) ) {
1341                 return false;
1342             }
1343             if ( !i_m_all21.getState( "cde", "0" ).contains( "C" ) ) {
1344                 return false;
1345             }
1346             if ( !i_m_all21.getState( "cde", "0" ).contains( "G" ) ) {
1347                 return false;
1348             }
1349             final FitchParsimony<String> fitch3 = new FitchParsimony<String>();
1350             final PhylogenyFactory factory3 = ParserBasedPhylogenyFactory.getInstance();
1351             final String p3_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1352             final Phylogeny p3 = factory3.create( p3_str, new NHXParser() )[ 0 ];
1353             final CharacterStateMatrix<String> m3 = new BasicCharacterStateMatrix<String>( 6, 1 );
1354             m3.setIdentifier( 0, "a" );
1355             m3.setIdentifier( 1, "b" );
1356             m3.setIdentifier( 2, "c" );
1357             m3.setIdentifier( 3, "d" );
1358             m3.setIdentifier( 4, "e" );
1359             m3.setIdentifier( 5, "f" );
1360             m3.setCharacter( 0, "0" );
1361             m3.setState( "a", "0", "C" );
1362             m3.setState( "b", "0", "U" );
1363             m3.setState( "c", "0", "G" );
1364             m3.setState( "d", "0", "U" );
1365             m3.setState( "e", "0", "A" );
1366             m3.setState( "f", "0", "A" );
1367             fitch3.setReturnInternalStates( true );
1368             fitch3.setReturnGainLossMatrix( false );
1369             fitch3.execute( p3, m3 );
1370             final CharacterStateMatrix<String> i_m3 = fitch3.getInternalStatesMatrix();
1371             final CharacterStateMatrix<List<String>> i_m_all3 = fitch3.getInternalStatesMatrixPriorToTraceback();
1372             if ( fitch3.getCost() != 4 ) {
1373                 return false;
1374             }
1375             if ( !i_m3.getState( "ab", "0" ).equals( "U" ) ) {
1376                 return false;
1377             }
1378             if ( !i_m3.getState( "cd", "0" ).equals( "U" ) ) {
1379                 return false;
1380             }
1381             if ( !i_m3.getState( "cde", "0" ).equals( "U" ) ) {
1382                 return false;
1383             }
1384             if ( !i_m3.getState( "abcde", "0" ).equals( "U" ) ) {
1385                 return false;
1386             }
1387             if ( !i_m3.getState( "r", "0" ).equals( "A" ) ) {
1388                 return false;
1389             }
1390             if ( i_m_all3.getState( "cde", "0" ).size() != 3 ) {
1391                 return false;
1392             }
1393             if ( !i_m_all3.getState( "cde", "0" ).contains( "A" ) ) {
1394                 return false;
1395             }
1396             if ( !i_m_all3.getState( "cde", "0" ).contains( "G" ) ) {
1397                 return false;
1398             }
1399             if ( !i_m_all3.getState( "cde", "0" ).contains( "U" ) ) {
1400                 return false;
1401             }
1402             if ( i_m_all3.getState( "ab", "0" ).size() != 2 ) {
1403                 return false;
1404             }
1405             if ( !i_m_all3.getState( "ab", "0" ).contains( "C" ) ) {
1406                 return false;
1407             }
1408             if ( !i_m_all3.getState( "ab", "0" ).contains( "U" ) ) {
1409                 return false;
1410             }
1411             if ( i_m_all3.getState( "cd", "0" ).size() != 2 ) {
1412                 return false;
1413             }
1414             if ( !i_m_all3.getState( "cd", "0" ).contains( "G" ) ) {
1415                 return false;
1416             }
1417             if ( !i_m_all3.getState( "cd", "0" ).contains( "U" ) ) {
1418                 return false;
1419             }
1420             if ( i_m_all3.getState( "abcde", "0" ).size() != 1 ) {
1421                 return false;
1422             }
1423             if ( !i_m_all3.getState( "abcde", "0" ).contains( "U" ) ) {
1424                 return false;
1425             }
1426             if ( i_m_all3.getState( "r", "0" ).size() != 2 ) {
1427                 return false;
1428             }
1429             if ( !i_m_all3.getState( "r", "0" ).contains( "A" ) ) {
1430                 return false;
1431             }
1432             if ( !i_m_all3.getState( "r", "0" ).contains( "U" ) ) {
1433                 return false;
1434             }
1435             final FitchParsimony<BinaryStates> fitch4 = new FitchParsimony<BinaryStates>();
1436             final PhylogenyFactory factory4 = ParserBasedPhylogenyFactory.getInstance();
1437             final String p4_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1438             final Phylogeny p4 = factory4.create( p4_str, new NHXParser() )[ 0 ];
1439             final CharacterStateMatrix<BinaryStates> m4 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1440             m4.setIdentifier( 0, "a" );
1441             m4.setIdentifier( 1, "b" );
1442             m4.setIdentifier( 2, "c" );
1443             m4.setIdentifier( 3, "d" );
1444             m4.setIdentifier( 4, "e" );
1445             m4.setIdentifier( 5, "f" );
1446             m4.setCharacter( 0, "0" );
1447             m4.setState( "a", "0", PRESENT );
1448             m4.setState( "b", "0", ABSENT );
1449             m4.setState( "c", "0", PRESENT );
1450             m4.setState( "d", "0", PRESENT );
1451             m4.setState( "e", "0", ABSENT );
1452             m4.setState( "f", "0", ABSENT );
1453             fitch4.setReturnInternalStates( true );
1454             fitch4.setReturnGainLossMatrix( true );
1455             fitch4.execute( p4, m4 );
1456             final CharacterStateMatrix<GainLossStates> gl_m_4 = fitch4.getGainLossMatrix();
1457             if ( fitch4.getCost() != 2 ) {
1458                 return false;
1459             }
1460             if ( fitch4.getTotalLosses() != 0 ) {
1461                 return false;
1462             }
1463             if ( fitch4.getTotalGains() != 2 ) {
1464                 return false;
1465             }
1466             if ( fitch4.getTotalUnchanged() != 9 ) {
1467                 return false;
1468             }
1469             if ( gl_m_4.getState( "a", "0" ) != GAIN ) {
1470                 return false;
1471             }
1472             if ( gl_m_4.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1473                 return false;
1474             }
1475             if ( gl_m_4.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1476                 return false;
1477             }
1478             if ( gl_m_4.getState( "cd", "0" ) != GAIN ) {
1479                 return false;
1480             }
1481             if ( gl_m_4.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1482                 return false;
1483             }
1484             final FitchParsimony<BinaryStates> fitch5 = new FitchParsimony<BinaryStates>();
1485             final PhylogenyFactory factory5 = ParserBasedPhylogenyFactory.getInstance();
1486             final String p5_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1487             final Phylogeny p5 = factory5.create( p5_str, new NHXParser() )[ 0 ];
1488             final CharacterStateMatrix<BinaryStates> m5 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1489             m5.setIdentifier( 0, "a" );
1490             m5.setIdentifier( 1, "b" );
1491             m5.setIdentifier( 2, "c" );
1492             m5.setIdentifier( 3, "d" );
1493             m5.setIdentifier( 4, "e" );
1494             m5.setIdentifier( 5, "f" );
1495             m5.setCharacter( 0, "0" );
1496             m5.setState( "a", "0", PRESENT );
1497             m5.setState( "b", "0", ABSENT );
1498             m5.setState( "c", "0", PRESENT );
1499             m5.setState( "d", "0", ABSENT );
1500             m5.setState( "e", "0", PRESENT );
1501             m5.setState( "f", "0", ABSENT );
1502             fitch5.setReturnInternalStates( true );
1503             fitch5.setReturnGainLossMatrix( true );
1504             fitch5.execute( p5, m5 );
1505             final CharacterStateMatrix<GainLossStates> gl_m_5 = fitch5.getGainLossMatrix();
1506             if ( fitch5.getCost() != 3 ) {
1507                 return false;
1508             }
1509             if ( fitch5.getTotalLosses() != 2 ) {
1510                 return false;
1511             }
1512             if ( fitch5.getTotalGains() != 1 ) {
1513                 return false;
1514             }
1515             if ( fitch5.getTotalUnchanged() != 8 ) {
1516                 return false;
1517             }
1518             if ( gl_m_5.getState( "abcde", "0" ) != GAIN ) {
1519                 return false;
1520             }
1521             if ( gl_m_5.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1522                 return false;
1523             }
1524             if ( gl_m_5.getState( "b", "0" ) != LOSS ) {
1525                 return false;
1526             }
1527             if ( gl_m_5.getState( "d", "0" ) != LOSS ) {
1528                 return false;
1529             }
1530             if ( gl_m_5.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1531                 return false;
1532             }
1533             final FitchParsimony<BinaryStates> fitch6 = new FitchParsimony<BinaryStates>();
1534             final PhylogenyFactory factory6 = ParserBasedPhylogenyFactory.getInstance();
1535             final String p6_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1536             final Phylogeny p6 = factory6.create( p6_str, new NHXParser() )[ 0 ];
1537             final CharacterStateMatrix<BinaryStates> m6 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1538             m6.setIdentifier( 0, "a" );
1539             m6.setIdentifier( 1, "b" );
1540             m6.setIdentifier( 2, "c" );
1541             m6.setIdentifier( 3, "d" );
1542             m6.setIdentifier( 4, "e" );
1543             m6.setIdentifier( 5, "f" );
1544             m6.setCharacter( 0, "0" );
1545             m6.setState( "a", "0", PRESENT );
1546             m6.setState( "b", "0", ABSENT );
1547             m6.setState( "c", "0", PRESENT );
1548             m6.setState( "d", "0", PRESENT );
1549             m6.setState( "e", "0", ABSENT );
1550             m6.setState( "f", "0", PRESENT );
1551             fitch6.setReturnInternalStates( true );
1552             fitch6.setReturnGainLossMatrix( true );
1553             fitch6.execute( p6, m6 );
1554             final CharacterStateMatrix<GainLossStates> gl_m_6 = fitch6.getGainLossMatrix();
1555             if ( fitch6.getCost() != 2 ) {
1556                 return false;
1557             }
1558             if ( fitch6.getTotalLosses() != 2 ) {
1559                 return false;
1560             }
1561             if ( fitch6.getTotalGains() != 0 ) {
1562                 return false;
1563             }
1564             if ( fitch6.getTotalUnchanged() != 9 ) {
1565                 return false;
1566             }
1567             if ( gl_m_6.getState( "abcde", "0" ) != UNCHANGED_PRESENT ) {
1568                 return false;
1569             }
1570             if ( gl_m_6.getState( "r", "0" ) != UNCHANGED_PRESENT ) {
1571                 return false;
1572             }
1573             if ( gl_m_6.getState( "b", "0" ) != LOSS ) {
1574                 return false;
1575             }
1576             if ( gl_m_6.getState( "e", "0" ) != LOSS ) {
1577                 return false;
1578             }
1579             final FitchParsimony<BinaryStates> fitch7 = new FitchParsimony<BinaryStates>();
1580             final PhylogenyFactory factory7 = ParserBasedPhylogenyFactory.getInstance();
1581             final String p7_str = "(((a,b)ab,(c,d)cd)abcd,((e,f)ef,(g,h)gh)efgh)r";
1582             final Phylogeny p7 = factory7.create( p7_str, new NHXParser() )[ 0 ];
1583             final CharacterStateMatrix<BinaryStates> m7 = new BasicCharacterStateMatrix<BinaryStates>( 8, 1 );
1584             m7.setIdentifier( 0, "a" );
1585             m7.setIdentifier( 1, "b" );
1586             m7.setIdentifier( 2, "c" );
1587             m7.setIdentifier( 3, "d" );
1588             m7.setIdentifier( 4, "e" );
1589             m7.setIdentifier( 5, "f" );
1590             m7.setIdentifier( 6, "g" );
1591             m7.setIdentifier( 7, "h" );
1592             m7.setCharacter( 0, "0" );
1593             m7.setState( "a", "0", PRESENT );
1594             m7.setState( "b", "0", ABSENT );
1595             m7.setState( "c", "0", PRESENT );
1596             m7.setState( "d", "0", ABSENT );
1597             m7.setState( "e", "0", PRESENT );
1598             m7.setState( "f", "0", ABSENT );
1599             m7.setState( "g", "0", PRESENT );
1600             m7.setState( "h", "0", ABSENT );
1601             fitch7.setReturnInternalStates( true );
1602             fitch7.setReturnGainLossMatrix( true );
1603             fitch7.execute( p7, m7 );
1604             final CharacterStateMatrix<GainLossStates> gl_m_7 = fitch7.getGainLossMatrix();
1605             if ( fitch7.getCost() != 4 ) {
1606                 return false;
1607             }
1608             if ( fitch7.getTotalLosses() != 0 ) {
1609                 return false;
1610             }
1611             if ( fitch7.getTotalGains() != 4 ) {
1612                 return false;
1613             }
1614             if ( fitch7.getTotalUnchanged() != 11 ) {
1615                 return false;
1616             }
1617             if ( gl_m_7.getState( "a", "0" ) != GAIN ) {
1618                 return false;
1619             }
1620             if ( gl_m_7.getState( "c", "0" ) != GAIN ) {
1621                 return false;
1622             }
1623             if ( gl_m_7.getState( "e", "0" ) != GAIN ) {
1624                 return false;
1625             }
1626             if ( gl_m_7.getState( "g", "0" ) != GAIN ) {
1627                 return false;
1628             }
1629             if ( gl_m_7.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1630                 return false;
1631             }
1632             fitch7.setReturnInternalStates( true );
1633             fitch7.setReturnGainLossMatrix( true );
1634             fitch7.setUseLast( true );
1635             fitch7.execute( p7, m7 );
1636             final CharacterStateMatrix<GainLossStates> gl_m_71 = fitch7.getGainLossMatrix();
1637             if ( fitch7.getCost() != 4 ) {
1638                 return false;
1639             }
1640             if ( fitch7.getTotalLosses() != 4 ) {
1641                 return false;
1642             }
1643             if ( fitch7.getTotalGains() != 0 ) {
1644                 return false;
1645             }
1646             if ( fitch7.getTotalUnchanged() != 11 ) {
1647                 return false;
1648             }
1649             if ( gl_m_71.getState( "b", "0" ) != LOSS ) {
1650                 return false;
1651             }
1652             if ( gl_m_71.getState( "d", "0" ) != LOSS ) {
1653                 return false;
1654             }
1655             if ( gl_m_71.getState( "f", "0" ) != LOSS ) {
1656                 return false;
1657             }
1658             if ( gl_m_71.getState( "h", "0" ) != LOSS ) {
1659                 return false;
1660             }
1661             if ( gl_m_71.getState( "r", "0" ) != UNCHANGED_PRESENT ) {
1662                 return false;
1663             }
1664             final FitchParsimony<BinaryStates> fitch8 = new FitchParsimony<BinaryStates>();
1665             final PhylogenyFactory factory8 = ParserBasedPhylogenyFactory.getInstance();
1666             final String p8_str = "(((a,b)ab,(c,d)cd)abcd,((e,f)ef,(g,h)gh)efgh)r";
1667             final Phylogeny p8 = factory8.create( p8_str, new NHXParser() )[ 0 ];
1668             final CharacterStateMatrix<BinaryStates> m8 = new BasicCharacterStateMatrix<BinaryStates>( 8, 1 );
1669             m8.setIdentifier( 0, "a" );
1670             m8.setIdentifier( 1, "b" );
1671             m8.setIdentifier( 2, "c" );
1672             m8.setIdentifier( 3, "d" );
1673             m8.setIdentifier( 4, "e" );
1674             m8.setIdentifier( 5, "f" );
1675             m8.setIdentifier( 6, "g" );
1676             m8.setIdentifier( 7, "h" );
1677             m8.setCharacter( 0, "0" );
1678             m8.setState( "a", "0", PRESENT );
1679             m8.setState( "b", "0", PRESENT );
1680             m8.setState( "c", "0", PRESENT );
1681             m8.setState( "d", "0", ABSENT );
1682             m8.setState( "e", "0", ABSENT );
1683             m8.setState( "f", "0", ABSENT );
1684             m8.setState( "g", "0", ABSENT );
1685             m8.setState( "h", "0", ABSENT );
1686             fitch8.setReturnInternalStates( true );
1687             fitch8.setReturnGainLossMatrix( true );
1688             fitch8.execute( p8, m8 );
1689             final CharacterStateMatrix<GainLossStates> gl_m_8 = fitch8.getGainLossMatrix();
1690             if ( fitch8.getCost() != 2 ) {
1691                 return false;
1692             }
1693             if ( fitch8.getTotalLosses() != 1 ) {
1694                 return false;
1695             }
1696             if ( fitch8.getTotalGains() != 1 ) {
1697                 return false;
1698             }
1699             if ( fitch8.getTotalUnchanged() != 13 ) {
1700                 return false;
1701             }
1702             if ( gl_m_8.getState( "d", "0" ) != LOSS ) {
1703                 return false;
1704             }
1705             if ( gl_m_8.getState( "abcd", "0" ) != GAIN ) {
1706                 return false;
1707             }
1708             final FitchParsimony<BinaryStates> fitch9 = new FitchParsimony<BinaryStates>();
1709             final PhylogenyFactory factory9 = ParserBasedPhylogenyFactory.getInstance();
1710             final String p9_str = "(((a,b)ab,c)abc,d)abcd";
1711             final Phylogeny p9 = factory9.create( p9_str, new NHXParser() )[ 0 ];
1712             final CharacterStateMatrix<BinaryStates> m9 = new BasicCharacterStateMatrix<BinaryStates>( 4, 1 );
1713             m9.setIdentifier( 0, "a" );
1714             m9.setIdentifier( 1, "b" );
1715             m9.setIdentifier( 2, "c" );
1716             m9.setIdentifier( 3, "d" );
1717             m9.setCharacter( 0, "0" );
1718             m9.setState( "a", "0", PRESENT );
1719             m9.setState( "b", "0", ABSENT );
1720             m9.setState( "c", "0", PRESENT );
1721             m9.setState( "d", "0", ABSENT );
1722             fitch9.setReturnInternalStates( true );
1723             fitch9.setReturnGainLossMatrix( true );
1724             fitch9.setUseLast( false );
1725             fitch9.execute( p9, m9 );
1726             final CharacterStateMatrix<GainLossStates> gl_m_9a = fitch9.getGainLossMatrix();
1727             if ( fitch9.getCost() != 2 ) {
1728                 return false;
1729             }
1730             if ( fitch9.getTotalLosses() != 1 ) {
1731                 return false;
1732             }
1733             if ( fitch9.getTotalGains() != 1 ) {
1734                 return false;
1735             }
1736             if ( fitch9.getTotalUnchanged() != 5 ) {
1737                 return false;
1738             }
1739             if ( gl_m_9a.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1740                 return false;
1741             }
1742             if ( gl_m_9a.getState( "b", "0" ) != LOSS ) {
1743                 return false;
1744             }
1745             if ( gl_m_9a.getState( "c", "0" ) != UNCHANGED_PRESENT ) {
1746                 return false;
1747             }
1748             if ( gl_m_9a.getState( "d", "0" ) != UNCHANGED_ABSENT ) {
1749                 return false;
1750             }
1751             if ( gl_m_9a.getState( "ab", "0" ) != UNCHANGED_PRESENT ) {
1752                 return false;
1753             }
1754             if ( gl_m_9a.getState( "abc", "0" ) != GAIN ) {
1755                 return false;
1756             }
1757             if ( gl_m_9a.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1758                 return false;
1759             }
1760             fitch9.setUseLast( true );
1761             fitch9.execute( p9, m9 );
1762             final CharacterStateMatrix<GainLossStates> gl_m_9b = fitch9.getGainLossMatrix();
1763             if ( fitch9.getCost() != 2 ) {
1764                 return false;
1765             }
1766             if ( fitch9.getTotalLosses() != 2 ) {
1767                 return false;
1768             }
1769             if ( fitch9.getTotalGains() != 0 ) {
1770                 return false;
1771             }
1772             if ( fitch9.getTotalUnchanged() != 5 ) {
1773                 return false;
1774             }
1775             if ( gl_m_9b.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1776                 return false;
1777             }
1778             if ( gl_m_9b.getState( "b", "0" ) != LOSS ) {
1779                 return false;
1780             }
1781             if ( gl_m_9b.getState( "c", "0" ) != UNCHANGED_PRESENT ) {
1782                 return false;
1783             }
1784             if ( gl_m_9b.getState( "d", "0" ) != LOSS ) {
1785                 return false;
1786             }
1787             if ( gl_m_9b.getState( "ab", "0" ) != UNCHANGED_PRESENT ) {
1788                 return false;
1789             }
1790             if ( gl_m_9b.getState( "abc", "0" ) != UNCHANGED_PRESENT ) {
1791                 return false;
1792             }
1793             if ( gl_m_9b.getState( "abcd", "0" ) != UNCHANGED_PRESENT ) {
1794                 return false;
1795             }
1796             fitch9.setUseLast( false );
1797             fitch9.setRandomize( true );
1798             fitch9.setRandomNumberSeed( 8722445 );
1799             fitch9.execute( p9, m9 );
1800             fitch9.getGainLossMatrix();
1801             if ( fitch9.getCost() != 2 ) {
1802                 return false;
1803             }
1804             if ( fitch9.getTotalLosses() != 1 ) {
1805                 return false;
1806             }
1807             if ( fitch9.getTotalGains() != 1 ) {
1808                 return false;
1809             }
1810             if ( fitch9.getTotalUnchanged() != 5 ) {
1811                 return false;
1812             }
1813             final FitchParsimony<BinaryStates> fitch10 = new FitchParsimony<BinaryStates>();
1814             final PhylogenyFactory factory10 = ParserBasedPhylogenyFactory.getInstance();
1815             final String p10_str = "((((a,b)ab,c)abc,d)abcd,e)abcde";
1816             final Phylogeny p10 = factory10.create( p10_str, new NHXParser() )[ 0 ];
1817             final CharacterStateMatrix<BinaryStates> m10 = new BasicCharacterStateMatrix<BinaryStates>( 5, 1 );
1818             m10.setIdentifier( 0, "a" );
1819             m10.setIdentifier( 1, "b" );
1820             m10.setIdentifier( 2, "c" );
1821             m10.setIdentifier( 3, "d" );
1822             m10.setIdentifier( 4, "e" );
1823             m10.setCharacter( 0, "0" );
1824             m10.setState( "a", "0", PRESENT );
1825             m10.setState( "b", "0", ABSENT );
1826             m10.setState( "c", "0", ABSENT );
1827             m10.setState( "d", "0", PRESENT );
1828             m10.setState( "e", "0", ABSENT );
1829             fitch10.setReturnInternalStates( true );
1830             fitch10.setReturnGainLossMatrix( true );
1831             fitch10.setUseLast( false );
1832             fitch10.execute( p10, m10 );
1833             final CharacterStateMatrix<GainLossStates> gl_m_10a = fitch10.getGainLossMatrix();
1834             if ( fitch10.getCost() != 2 ) {
1835                 return false;
1836             }
1837             if ( fitch10.getTotalLosses() != 0 ) {
1838                 return false;
1839             }
1840             if ( fitch10.getTotalGains() != 2 ) {
1841                 return false;
1842             }
1843             if ( fitch10.getTotalUnchanged() != 7 ) {
1844                 return false;
1845             }
1846             if ( gl_m_10a.getState( "a", "0" ) != GAIN ) {
1847                 return false;
1848             }
1849             if ( gl_m_10a.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1850                 return false;
1851             }
1852             if ( gl_m_10a.getState( "c", "0" ) != UNCHANGED_ABSENT ) {
1853                 return false;
1854             }
1855             if ( gl_m_10a.getState( "d", "0" ) != GAIN ) {
1856                 return false;
1857             }
1858             if ( gl_m_10a.getState( "e", "0" ) != UNCHANGED_ABSENT ) {
1859                 return false;
1860             }
1861             if ( gl_m_10a.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1862                 return false;
1863             }
1864             if ( gl_m_10a.getState( "abc", "0" ) != UNCHANGED_ABSENT ) {
1865                 return false;
1866             }
1867             if ( gl_m_10a.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1868                 return false;
1869             }
1870             if ( gl_m_10a.getState( "abcde", "0" ) != UNCHANGED_ABSENT ) {
1871                 return false;
1872             }
1873             fitch10.setUseLast( true );
1874             fitch10.execute( p10, m10 );
1875             final CharacterStateMatrix<GainLossStates> gl_m_10b = fitch10.getGainLossMatrix();
1876             if ( fitch10.getCost() != 2 ) {
1877                 return false;
1878             }
1879             if ( fitch10.getTotalLosses() != 0 ) {
1880                 return false;
1881             }
1882             if ( fitch10.getTotalGains() != 2 ) {
1883                 return false;
1884             }
1885             if ( fitch10.getTotalUnchanged() != 7 ) {
1886                 return false;
1887             }
1888             if ( gl_m_10b.getState( "a", "0" ) != GAIN ) {
1889                 return false;
1890             }
1891             if ( gl_m_10b.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1892                 return false;
1893             }
1894             if ( gl_m_10b.getState( "c", "0" ) != UNCHANGED_ABSENT ) {
1895                 return false;
1896             }
1897             if ( gl_m_10b.getState( "d", "0" ) != GAIN ) {
1898                 return false;
1899             }
1900             if ( gl_m_10b.getState( "e", "0" ) != UNCHANGED_ABSENT ) {
1901                 return false;
1902             }
1903             if ( gl_m_10b.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1904                 return false;
1905             }
1906             if ( gl_m_10b.getState( "abc", "0" ) != UNCHANGED_ABSENT ) {
1907                 return false;
1908             }
1909             if ( gl_m_10b.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1910                 return false;
1911             }
1912             if ( gl_m_10b.getState( "abcde", "0" ) != UNCHANGED_ABSENT ) {
1913                 return false;
1914             }
1915         }
1916         catch ( final Exception e ) {
1917             e.printStackTrace( System.out );
1918             return false;
1919         }
1920         return true;
1921     }
1922
1923     private static boolean testNeighborJoining() {
1924         try {
1925             NeighborJoining nj = NeighborJoining.createInstance();
1926             final BasicSymmetricalDistanceMatrix m0 = new BasicSymmetricalDistanceMatrix( 4 );
1927             m0.setIdentifier( 0, "A" );
1928             m0.setIdentifier( 1, "B" );
1929             m0.setIdentifier( 2, "C" );
1930             m0.setIdentifier( 3, "D" );
1931             m0.setRow( "5 ", 1 );
1932             m0.setRow( "3 6 ", 2 );
1933             m0.setRow( "7.5 10.5 5.5", 3 );
1934             final Phylogeny p0 = nj.execute( m0 );
1935             p0.reRoot( p0.getNode( "D" ) );
1936             if ( isUnequal( p0.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1937                 return false;
1938             }
1939             if ( isUnequal( p0.getNode( "B" ).getDistanceToParent(), 4 ) ) {
1940                 return false;
1941             }
1942             if ( isUnequal( p0.getNode( "C" ).getDistanceToParent(), 0.5 ) ) {
1943                 return false;
1944             }
1945             if ( isUnequal( p0.getNode( "D" ).getDistanceToParent(), 2.5 ) ) {
1946                 return false;
1947             }
1948             if ( isUnequal( p0.getNode( "A" ).getParent().getDistanceToParent(), 1.5 ) ) {
1949                 return false;
1950             }
1951             if ( isUnequal( p0.getNode( "A" ).getParent().getParent().getDistanceToParent(), 2.5 ) ) {
1952                 return false;
1953             }
1954             nj = NeighborJoining.createInstance();
1955             final BasicSymmetricalDistanceMatrix m00 = new BasicSymmetricalDistanceMatrix( 4 );
1956             m00.setIdentifier( 0, "A" );
1957             m00.setIdentifier( 1, "B" );
1958             m00.setIdentifier( 2, "C" );
1959             m00.setIdentifier( 3, "D" );
1960             m00.setRow( "2.01 ", 1 );
1961             m00.setRow( "3 3.01 ", 2 );
1962             m00.setRow( "3.01 3.02 1.01", 3 );
1963             final Phylogeny p00 = nj.execute( m00 );
1964             p00.reRoot( p00.getNode( "D" ) );
1965             if ( isUnequal( p00.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1966                 return false;
1967             }
1968             if ( isUnequal( p00.getNode( "B" ).getDistanceToParent(), 1.01 ) ) {
1969                 return false;
1970             }
1971             if ( isUnequal( p00.getNode( "C" ).getDistanceToParent(), 0.5 ) ) {
1972                 return false;
1973             }
1974             if ( isUnequal( p00.getNode( "D" ).getDistanceToParent(), 0.255 ) ) {
1975                 return false;
1976             }
1977             if ( isUnequal( p00.getNode( "A" ).getParent().getDistanceToParent(), 1.5 ) ) {
1978                 return false;
1979             }
1980             if ( isUnequal( p00.getNode( "A" ).getParent().getParent().getDistanceToParent(), 0.255 ) ) {
1981                 return false;
1982             }
1983             BasicSymmetricalDistanceMatrix m = new BasicSymmetricalDistanceMatrix( 6 );
1984             m.setRow( "5", 1 );
1985             m.setRow( "4 7", 2 );
1986             m.setRow( "7 10 7", 3 );
1987             m.setRow( "6 9 6 5", 4 );
1988             m.setRow( "8 11 8 9 8", 5 );
1989             m.setIdentifier( 0, "A" );
1990             m.setIdentifier( 1, "B" );
1991             m.setIdentifier( 2, "C" );
1992             m.setIdentifier( 3, "D" );
1993             m.setIdentifier( 4, "E" );
1994             m.setIdentifier( 5, "F" );
1995             nj = NeighborJoining.createInstance();
1996             final Phylogeny p1 = nj.execute( m );
1997             p1.reRoot( p1.getNode( "F" ) );
1998             if ( isUnequal( p1.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1999                 return false;
2000             }
2001             if ( isUnequal( p1.getNode( "B" ).getDistanceToParent(), 4 ) ) {
2002                 return false;
2003             }
2004             if ( isUnequal( p1.getNode( "C" ).getDistanceToParent(), 2 ) ) {
2005                 return false;
2006             }
2007             if ( isUnequal( p1.getNode( "D" ).getDistanceToParent(), 3 ) ) {
2008                 return false;
2009             }
2010             if ( isUnequal( p1.getNode( "E" ).getDistanceToParent(), 2 ) ) {
2011                 return false;
2012             }
2013             if ( isUnequal( p1.getNode( "F" ).getDistanceToParent(), 2.5 ) ) {
2014                 return false;
2015             }
2016             if ( isUnequal( p1.getNode( "A" ).getParent().getDistanceToParent(), 1 ) ) {
2017                 return false;
2018             }
2019             if ( isUnequal( p1.getNode( "A" ).getParent().getParent().getDistanceToParent(), 1 ) ) {
2020                 return false;
2021             }
2022             if ( isUnequal( p1.getNode( "A" ).getParent().getParent().getParent().getDistanceToParent(), 2.5 ) ) {
2023                 return false;
2024             }
2025             if ( isUnequal( p1.getNode( "B" ).getParent().getDistanceToParent(), 1 ) ) {
2026                 return false;
2027             }
2028             if ( isUnequal( p1.getNode( "D" ).getParent().getDistanceToParent(), 1 ) ) {
2029                 return false;
2030             }
2031             if ( isUnequal( p1.getNode( "E" ).getParent().getDistanceToParent(), 1 ) ) {
2032                 return false;
2033             }
2034             m = new BasicSymmetricalDistanceMatrix( 7 );
2035             m.setIdentifier( 0, "Bovine" );
2036             m.setIdentifier( 1, "Mouse" );
2037             m.setIdentifier( 2, "Gibbon" );
2038             m.setIdentifier( 3, "Orang" );
2039             m.setIdentifier( 4, "Gorilla" );
2040             m.setIdentifier( 5, "Chimp" );
2041             m.setIdentifier( 6, "Human" );
2042             m.setRow( "0.00000 1.68660 1.71980 1.66060 1.52430 1.60430 1.59050", 0 );
2043             m.setRow( "1.68660 0.00000 1.52320 1.48410 1.44650 1.43890 1.46290", 1 );
2044             m.setRow( "1.71980 1.52320 0.00000 0.71150 0.59580 0.61790 0.55830", 2 );
2045             m.setRow( "1.66060 1.48410 0.71150 0.00000 0.46310 0.50610 0.47100", 3 );
2046             m.setRow( "1.52430 1.44650 0.59580 0.46310 0.00000 0.34840 0.30830", 4 );
2047             m.setRow( "1.60430 1.43890 0.61790 0.50610 0.34840 0.00000 0.26920", 5 );
2048             m.setRow( "1.59050 1.46290 0.55830 0.47100 0.30830 0.26920 0.00000", 6 );
2049             nj = NeighborJoining.createInstance( false, 6 );
2050             final Phylogeny p2 = nj.execute( m );
2051             p2.reRoot( p2.getNode( "Bovine" ) );
2052             if ( isUnequal( p2.getNode( "Chimp" ).getDistanceToParent(), 0.151675 ) ) {
2053                 return false;
2054             }
2055             if ( isUnequal( p2.getNode( "Human" ).getDistanceToParent(), 0.117525 ) ) {
2056                 return false;
2057             }
2058             if ( isUnequal( p2.getNode( "Gorilla" ).getDistanceToParent(), 0.153932 ) ) {
2059                 return false;
2060             }
2061             if ( isUnequal( p2.getNode( "Orang" ).getDistanceToParent(), 0.284694 ) ) {
2062                 return false;
2063             }
2064             if ( isUnequal( p2.getNode( "Gibbon" ).getDistanceToParent(), 0.357931 ) ) {
2065                 return false;
2066             }
2067             if ( isUnequal( p2.getNode( "Mouse" ).getDistanceToParent(), 0.76891 ) ) {
2068                 return false;
2069             }
2070             if ( isUnequal( p2.getNode( "Bovine" ).getDistanceToParent(), 0.458845 ) ) {
2071                 return false;
2072             }
2073             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getDistanceToParent(), 0.039819 ) ) {
2074                 return false;
2075             }
2076             if ( isUnequal( p2.getNode( "Human" ).getParent().getDistanceToParent(), 0.039819 ) ) {
2077                 return false;
2078             }
2079             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getDistanceToParent(), 0.026956 ) ) {
2080                 return false;
2081             }
2082             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getDistanceToParent(), 0.046481 ) ) {
2083                 return false;
2084             }
2085             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getParent().getDistanceToParent(),
2086                             0.420269 ) ) {
2087                 return false;
2088             }
2089             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getParent().getParent()
2090                     .getDistanceToParent(), 0.458845 ) ) {
2091                 return false;
2092             }
2093             m = new BasicSymmetricalDistanceMatrix( 4 );
2094             m.setIdentifier( 0, "A" );
2095             m.setIdentifier( 1, "B" );
2096             m.setIdentifier( 2, "C" );
2097             m.setIdentifier( 3, "D" );
2098             m.setRow( "0.00 0.95 0.17 0.98", 0 );
2099             m.setRow( "0.95 0.00 1.02 1.83", 1 );
2100             m.setRow( "0.17 1.02 0.00 1.01", 2 );
2101             m.setRow( "0.98 1.83 1.01 0.00", 3 );
2102             final Phylogeny p3 = nj.execute( m );
2103             p3.reRoot( p3.getNode( "C" ) );
2104             if ( isUnequal( p3.getNode( "A" ).getDistanceToParent(), 0.05 ) ) {
2105                 return false;
2106             }
2107             if ( isUnequal( p3.getNode( "B" ).getDistanceToParent(), 0.90 ) ) {
2108                 return false;
2109             }
2110             if ( !isEqual( p3.getNode( "C" ).getDistanceToParent(), 0.05 ) ) {
2111                 return false;
2112             }
2113             if ( !isEqual( p3.getNode( "D" ).getDistanceToParent(), 0.91 ) ) {
2114                 return false;
2115             }
2116             if ( isUnequal( p3.getNode( "A" ).getParent().getDistanceToParent(), 0.02 ) ) {
2117                 return false;
2118             }
2119             if ( isUnequal( p3.getNode( "A" ).getParent().getParent().getDistanceToParent(), 0.05 ) ) {
2120                 return false;
2121             }
2122             //if ( TIME ) {
2123             //    timeNeighborJoining();
2124             //}
2125         }
2126         catch ( final Exception e ) {
2127             e.printStackTrace( System.out );
2128             return false;
2129         }
2130         return true;
2131     }
2132
2133     private static boolean testSymmetricalDistanceMatrixParser() {
2134         try {
2135             final String l = ForesterUtil.getLineSeparator();
2136             StringBuffer source = new StringBuffer();
2137             source.append( " 4" + l );
2138             source.append( "A 0 0 0 0" + l );
2139             source.append( "B 1 0 0 0" + l );
2140             source.append( "C 2 4 0 0" + l );
2141             source.append( "D 3 5 6 0" + l );
2142             source.append( l );
2143             source.append( " 4" + l );
2144             source.append( "A 0   11  12  13" + l );
2145             source.append( "B 11  0   14  15" + l );
2146             source.append( "C 12  14  0   16" + l );
2147             source.append( "D 13  15  16  0" + l );
2148             source.append( l );
2149             source.append( l );
2150             source.append( "     " + l );
2151             source.append( " 4" + l );
2152             source.append( " A        0     " + l );
2153             source.append( " B            21 0" + l );
2154             source.append( " C            22 24    0  " + l );
2155             source.append( " # 2 222 2 2 " + l );
2156             source.append( " D            23 25 26 0" + l );
2157             source.append( l );
2158             source.append( l );
2159             source.append( "     " + l );
2160             final SymmetricalDistanceMatrixParser p0 = SymmetricalDistanceMatrixParser.createInstance();
2161             final DistanceMatrix[] ma0 = p0.parse( source.toString() );
2162             if ( ma0.length != 3 ) {
2163                 return false;
2164             }
2165             if ( !isEqual( ma0[ 0 ].getValue( 0, 0 ), 0 ) ) {
2166                 return false;
2167             }
2168             if ( !isEqual( ma0[ 0 ].getValue( 1, 0 ), 1 ) ) {
2169                 return false;
2170             }
2171             if ( !isEqual( ma0[ 0 ].getValue( 2, 0 ), 2 ) ) {
2172                 return false;
2173             }
2174             if ( !isEqual( ma0[ 0 ].getValue( 3, 0 ), 3 ) ) {
2175                 return false;
2176             }
2177             if ( !isEqual( ma0[ 0 ].getValue( 0, 1 ), 1 ) ) {
2178                 return false;
2179             }
2180             if ( !isEqual( ma0[ 0 ].getValue( 1, 1 ), 0 ) ) {
2181                 return false;
2182             }
2183             if ( !isEqual( ma0[ 0 ].getValue( 2, 1 ), 4 ) ) {
2184                 return false;
2185             }
2186             if ( !isEqual( ma0[ 0 ].getValue( 3, 1 ), 5 ) ) {
2187                 return false;
2188             }
2189             if ( !isEqual( ma0[ 1 ].getValue( 0, 0 ), 0 ) ) {
2190                 return false;
2191             }
2192             if ( !isEqual( ma0[ 1 ].getValue( 1, 0 ), 11 ) ) {
2193                 return false;
2194             }
2195             if ( !isEqual( ma0[ 1 ].getValue( 2, 0 ), 12 ) ) {
2196                 return false;
2197             }
2198             if ( !isEqual( ma0[ 1 ].getValue( 3, 0 ), 13 ) ) {
2199                 return false;
2200             }
2201             if ( !isEqual( ma0[ 1 ].getValue( 0, 1 ), 11 ) ) {
2202                 return false;
2203             }
2204             if ( !isEqual( ma0[ 1 ].getValue( 1, 1 ), 0 ) ) {
2205                 return false;
2206             }
2207             if ( !isEqual( ma0[ 1 ].getValue( 2, 1 ), 14 ) ) {
2208                 return false;
2209             }
2210             if ( !isEqual( ma0[ 1 ].getValue( 3, 1 ), 15 ) ) {
2211                 return false;
2212             }
2213             if ( !isEqual( ma0[ 2 ].getValue( 0, 0 ), 0 ) ) {
2214                 return false;
2215             }
2216             if ( !isEqual( ma0[ 2 ].getValue( 1, 0 ), 21 ) ) {
2217                 return false;
2218             }
2219             if ( !isEqual( ma0[ 2 ].getValue( 2, 0 ), 22 ) ) {
2220                 return false;
2221             }
2222             if ( !isEqual( ma0[ 2 ].getValue( 3, 0 ), 23 ) ) {
2223                 return false;
2224             }
2225             if ( !isEqual( ma0[ 2 ].getValue( 0, 1 ), 21 ) ) {
2226                 return false;
2227             }
2228             if ( !isEqual( ma0[ 2 ].getValue( 1, 1 ), 0 ) ) {
2229                 return false;
2230             }
2231             if ( !isEqual( ma0[ 2 ].getValue( 2, 1 ), 24 ) ) {
2232                 return false;
2233             }
2234             if ( !isEqual( ma0[ 2 ].getValue( 3, 1 ), 25 ) ) {
2235                 return false;
2236             }
2237             source = new StringBuffer();
2238             source.append( "A 0 0 0 0" + l );
2239             source.append( "B 1 0 0 0" + l );
2240             source.append( "C 2 4 0 0" + l );
2241             source.append( "D 3 5 6 0" + l );
2242             source.append( " " + l );
2243             source.append( "A 0   11  12  13" + l );
2244             source.append( "B 11  0   14  15" + l );
2245             source.append( "C 12  14  0   16" + l );
2246             source.append( "D 13  15  16  0" + l );
2247             source.append( l );
2248             source.append( " A        0     " + l );
2249             source.append( " B            21 0" + l );
2250             source.append( " C            22 24    0  " + l );
2251             source.append( " # 2 222 2 2 " + l );
2252             source.append( " D            23 25 26 0" + l );
2253             final DistanceMatrix[] ma1 = p0.parse( source.toString() );
2254             if ( ma1.length != 3 ) {
2255                 return false;
2256             }
2257             if ( !isEqual( ma1[ 0 ].getValue( 0, 0 ), 0 ) ) {
2258                 return false;
2259             }
2260             if ( !isEqual( ma1[ 0 ].getValue( 1, 0 ), 1 ) ) {
2261                 return false;
2262             }
2263             if ( !isEqual( ma1[ 0 ].getValue( 2, 0 ), 2 ) ) {
2264                 return false;
2265             }
2266             if ( !isEqual( ma1[ 0 ].getValue( 3, 0 ), 3 ) ) {
2267                 return false;
2268             }
2269             if ( !isEqual( ma1[ 0 ].getValue( 0, 1 ), 1 ) ) {
2270                 return false;
2271             }
2272             if ( !isEqual( ma1[ 0 ].getValue( 1, 1 ), 0 ) ) {
2273                 return false;
2274             }
2275             if ( !isEqual( ma1[ 0 ].getValue( 2, 1 ), 4 ) ) {
2276                 return false;
2277             }
2278             if ( !isEqual( ma1[ 0 ].getValue( 3, 1 ), 5 ) ) {
2279                 return false;
2280             }
2281             if ( !isEqual( ma1[ 1 ].getValue( 0, 0 ), 0 ) ) {
2282                 return false;
2283             }
2284             if ( !isEqual( ma1[ 1 ].getValue( 1, 0 ), 11 ) ) {
2285                 return false;
2286             }
2287             if ( !isEqual( ma1[ 1 ].getValue( 2, 0 ), 12 ) ) {
2288                 return false;
2289             }
2290             if ( !isEqual( ma1[ 1 ].getValue( 3, 0 ), 13 ) ) {
2291                 return false;
2292             }
2293             if ( !isEqual( ma1[ 1 ].getValue( 0, 1 ), 11 ) ) {
2294                 return false;
2295             }
2296             if ( !isEqual( ma1[ 1 ].getValue( 1, 1 ), 0 ) ) {
2297                 return false;
2298             }
2299             if ( !isEqual( ma1[ 1 ].getValue( 2, 1 ), 14 ) ) {
2300                 return false;
2301             }
2302             if ( !isEqual( ma1[ 1 ].getValue( 3, 1 ), 15 ) ) {
2303                 return false;
2304             }
2305             if ( !isEqual( ma1[ 2 ].getValue( 0, 0 ), 0 ) ) {
2306                 return false;
2307             }
2308             if ( !isEqual( ma1[ 2 ].getValue( 1, 0 ), 21 ) ) {
2309                 return false;
2310             }
2311             if ( !isEqual( ma1[ 2 ].getValue( 2, 0 ), 22 ) ) {
2312                 return false;
2313             }
2314             if ( !isEqual( ma1[ 2 ].getValue( 3, 0 ), 23 ) ) {
2315                 return false;
2316             }
2317             if ( !isEqual( ma1[ 2 ].getValue( 0, 1 ), 21 ) ) {
2318                 return false;
2319             }
2320             if ( !isEqual( ma1[ 2 ].getValue( 1, 1 ), 0 ) ) {
2321                 return false;
2322             }
2323             if ( !isEqual( ma1[ 2 ].getValue( 2, 1 ), 24 ) ) {
2324                 return false;
2325             }
2326             if ( !isEqual( ma1[ 2 ].getValue( 3, 1 ), 25 ) ) {
2327                 return false;
2328             }
2329             source = new StringBuffer();
2330             source.append( "A 0" + l );
2331             source.append( "B 10 0" + l );
2332             final DistanceMatrix[] ma2 = p0.parse( source.toString() );
2333             if ( ma2.length != 1 ) {
2334                 return false;
2335             }
2336             if ( !isEqual( ma2[ 0 ].getValue( 0, 1 ), 10 ) ) {
2337                 return false;
2338             }
2339             source = new StringBuffer();
2340             source.append( " " + l );
2341             source.append( "#" + l );
2342             final DistanceMatrix[] ma3 = p0.parse( source.toString() );
2343             if ( ma3.length != 0 ) {
2344                 return false;
2345             }
2346             source = new StringBuffer();
2347             source.append( " " + l );
2348             source.append( "A 0   11  12  13" + l );
2349             source.append( "B     0   14  15" + l );
2350             source.append( "C         0   16" + l );
2351             source.append( "D              0" + l );
2352             source.append( l );
2353             source.append( "A 0 21  22  23" + l );
2354             source.append( "B 0 24  25" + l );
2355             source.append( "C 0 26" + l );
2356             source.append( "D 0" + l );
2357             p0.setInputMatrixType( SymmetricalDistanceMatrixParser.InputMatrixType.UPPER_TRIANGLE );
2358             final DistanceMatrix[] ma4 = p0.parse( source );
2359             if ( ma4.length != 2 ) {
2360                 return false;
2361             }
2362             if ( !isEqual( ma4[ 0 ].getValue( 0, 0 ), 0 ) ) {
2363                 return false;
2364             }
2365             if ( !isEqual( ma4[ 0 ].getValue( 1, 0 ), 11 ) ) {
2366                 return false;
2367             }
2368             if ( !isEqual( ma4[ 0 ].getValue( 2, 0 ), 12 ) ) {
2369                 return false;
2370             }
2371             if ( !isEqual( ma4[ 0 ].getValue( 3, 0 ), 13 ) ) {
2372                 return false;
2373             }
2374             if ( !isEqual( ma4[ 0 ].getValue( 0, 1 ), 11 ) ) {
2375                 return false;
2376             }
2377             if ( !isEqual( ma4[ 0 ].getValue( 1, 1 ), 0 ) ) {
2378                 return false;
2379             }
2380             if ( !isEqual( ma4[ 0 ].getValue( 2, 1 ), 14 ) ) {
2381                 return false;
2382             }
2383             if ( !isEqual( ma4[ 0 ].getValue( 3, 1 ), 15 ) ) {
2384                 return false;
2385             }
2386             if ( !isEqual( ma4[ 0 ].getValue( 0, 2 ), 12 ) ) {
2387                 return false;
2388             }
2389             if ( !isEqual( ma4[ 0 ].getValue( 1, 2 ), 14 ) ) {
2390                 return false;
2391             }
2392             if ( !isEqual( ma4[ 0 ].getValue( 2, 2 ), 0 ) ) {
2393                 return false;
2394             }
2395             if ( !isEqual( ma4[ 0 ].getValue( 3, 2 ), 16 ) ) {
2396                 return false;
2397             }
2398             if ( !isEqual( ma4[ 0 ].getValue( 0, 3 ), 13 ) ) {
2399                 return false;
2400             }
2401             if ( !isEqual( ma4[ 0 ].getValue( 1, 3 ), 15 ) ) {
2402                 return false;
2403             }
2404             if ( !isEqual( ma4[ 0 ].getValue( 2, 3 ), 16 ) ) {
2405                 return false;
2406             }
2407             if ( !isEqual( ma4[ 0 ].getValue( 3, 3 ), 0 ) ) {
2408                 return false;
2409             }
2410             source = new StringBuffer();
2411             source.append( " 4 " + l );
2412             source.append( "A 0   11  12  13" + l );
2413             source.append( "B     0   14  15" + l );
2414             source.append( "C         0   16" + l );
2415             source.append( "D              0" + l );
2416             source.append( " 4" + l );
2417             source.append( "A 0 21  22  23" + l );
2418             source.append( "B 0 24  25" + l );
2419             source.append( "C 0 26" + l );
2420             source.append( "D 0" + l );
2421             source.append( "     " + l );
2422             source.append( " 4" + l );
2423             source.append( "A 0 21  22  23" + l );
2424             source.append( "B 0 24  25" + l );
2425             source.append( "C 0 26" + l );
2426             source.append( "D 0" + l );
2427             source.append( l );
2428             source.append( "A 0 21  22  23" + l );
2429             source.append( "B 0 24  25" + l );
2430             source.append( "C 0 26" + l );
2431             source.append( "D 0" + l );
2432             p0.setInputMatrixType( SymmetricalDistanceMatrixParser.InputMatrixType.UPPER_TRIANGLE );
2433             final DistanceMatrix[] ma5 = p0.parse( source );
2434             if ( ma5.length != 4 ) {
2435                 return false;
2436             }
2437             if ( !isEqual( ma5[ 0 ].getValue( 0, 0 ), 0 ) ) {
2438                 return false;
2439             }
2440             if ( !isEqual( ma5[ 0 ].getValue( 1, 0 ), 11 ) ) {
2441                 return false;
2442             }
2443             if ( !isEqual( ma5[ 0 ].getValue( 2, 0 ), 12 ) ) {
2444                 return false;
2445             }
2446             if ( !isEqual( ma5[ 0 ].getValue( 3, 0 ), 13 ) ) {
2447                 return false;
2448             }
2449             if ( !isEqual( ma5[ 0 ].getValue( 0, 1 ), 11 ) ) {
2450                 return false;
2451             }
2452             if ( !isEqual( ma5[ 0 ].getValue( 1, 1 ), 0 ) ) {
2453                 return false;
2454             }
2455             if ( !isEqual( ma5[ 0 ].getValue( 2, 1 ), 14 ) ) {
2456                 return false;
2457             }
2458             if ( !isEqual( ma5[ 0 ].getValue( 3, 1 ), 15 ) ) {
2459                 return false;
2460             }
2461             if ( !isEqual( ma5[ 0 ].getValue( 0, 2 ), 12 ) ) {
2462                 return false;
2463             }
2464             if ( !isEqual( ma5[ 0 ].getValue( 1, 2 ), 14 ) ) {
2465                 return false;
2466             }
2467             if ( !isEqual( ma5[ 0 ].getValue( 2, 2 ), 0 ) ) {
2468                 return false;
2469             }
2470             if ( !isEqual( ma5[ 0 ].getValue( 3, 2 ), 16 ) ) {
2471                 return false;
2472             }
2473             if ( !isEqual( ma5[ 0 ].getValue( 0, 3 ), 13 ) ) {
2474                 return false;
2475             }
2476             if ( !isEqual( ma5[ 0 ].getValue( 1, 3 ), 15 ) ) {
2477                 return false;
2478             }
2479             if ( !isEqual( ma5[ 0 ].getValue( 2, 3 ), 16 ) ) {
2480                 return false;
2481             }
2482             if ( !isEqual( ma5[ 0 ].getValue( 3, 3 ), 0 ) ) {
2483                 return false;
2484             }
2485         }
2486         catch ( final Exception e ) {
2487             e.printStackTrace( System.out );
2488             return false;
2489         }
2490         return true;
2491     }
2492
2493     private static void timeNeighborJoining() {
2494         final NeighborJoining nj = NeighborJoining.createInstance();
2495         for( int n = 3; n <= 10; ++n ) {
2496             final int x = ( int ) Math.pow( 2, n );
2497             final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x );
2498             mt.randomize( new Date().getTime() );
2499             //  for( int i = 0; i < mt.getSize(); i++ ) {
2500             //      mt.setIdentifier( i, i + "i" );
2501             //  }
2502             //  System.out.println( mt.toStringBuffer( Format.PHYLIP ) );
2503             final long start_time = new Date().getTime();
2504             nj.execute( mt );
2505             System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" );
2506         }
2507         final NeighborJoiningX njx = NeighborJoiningX.createInstance();
2508         for( int n = 3; n <= 10; ++n ) {
2509             final int x = ( int ) Math.pow( 2, n );
2510             final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x );
2511             mt.randomize( new Date().getTime() );
2512             //  for( int i = 0; i < mt.getSize(); i++ ) {
2513             //      mt.setIdentifier( i, i + "i" );
2514             //  }
2515             //  System.out.println( mt.toStringBuffer( Format.PHYLIP ) );
2516             final long start_time = new Date().getTime();
2517             njx.execute( mt );
2518             System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" );
2519         }
2520     }
2521 }