Single column discrepancy and dynamic max-mini optimizations for quickly finding the most parsimonious evolutionary trees

Motivation: In the maximum parsimony (MP) method, the tree requiring the minimum number of changes (discrepancy) to explain the given set of DNA or amino acid sequences is chosen to represent their evolutionary relationships, To find the MP tree, the branch-and-bound algorithm is normally used, For a partial phylogenetic-tree (one that has a subset of the organisms) the traditional algorithm assigns a cost equal to the discrepancy of the partial phylogenetic-tree. We propose a single column discrepancy heuristic which increases this cost by predicting a minimum additional discrepancy needed to attach the sequences yet to be added to the partial phylogenetic-tree. A dynamic Max-mini order of sequence addition is also proposed to quickly terminate branch-and-bound search paths that are guaranteed to lean to suboptimal solutions. Results: We studied the running time of 47 problems generated from 17 data sets. The use of single column discrepancy heuristic speeded nl, the computation to 2.4-fold for static and 18.2-fold for dynamic search or der: The improvement appeared to increase exponentially with rite number of sequences. The proposed strategies are also likely to be useful in speeding rip the MP tree search rising heuristic searches that are based on branch-and-bound-like algorithms, Contact: s.kumar@asu.edu.