
PDA - Phylogenetic Diversity Algorithm version 0.1
--------------------------------------------------

Copyright (C) 2006 BUI Quang Minh, Steffen Klaere, Arndt von Haeseler 

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or   
(at your option) any later version. 

===========================================================================

DESCRIPTION:
------------

This software implements two efficient algorithms to solve the 
Phylogenetic Diversity (PD) problem as formulated by Faith (1992) as 
follows: Given a phylogenetic tree of n species (either bifurcating
or not), find a subset of k species whose subtree has maximal sum of
branch lengths. Our algorithms, gPDA and pPDA, apply two strategy,
namely greedy and pruning, to solve this problem in time O(nlogk) and
O(nlog(n-k)) respectively. Actual tests suggest that gPDA is more 
applicable when k < 0.7n, otherwise pPDA should be preferred.

===========================================================================

COMMAND-LINE OPTIONS:
---------------------

./pda [options]

Available options are follows:

  <user_tree>       User tree file in NEWICK format.
  -k <num_leaves>   Number of leaves to be preserved.
  -r <num_leaves>   Create a random tree and write to the <user_tree>.

  -g, --greedy      Only run the greedy algorithm.
  -p, --pruning     Only run the pruning algorithm.
  -b, --both        Run both algorithm.
  -e <file>         Parameters as regional/social diversity.


The <file> containing regional/social parameters must be in the following
format:
1. First line is a coefficient, which every branch length should
be multiplied with. 
2. The rest lines contain <n> parameters as the "importance" of <n> species.
These numbers can be written in several lines.

More information on those additional parameters can be found in Steel (2005).

===========================================================================

OUTPUTS:
--------

Resulting trees are written into:

<user_file>.<k>.greedy for greedy algorithm, and
<user_file>.<k>.pruning for pruning algorithm.

If you choose option to generate a random tree, it will be written to the
<user_file>.

===========================================================================

INSTALLATION:
-------------

    To build PDA from the sources you need a functional C++ compiler
    installed (This is usually the case on UNIX/Linux systems. For 
    Windows you might want to obtain CygWin or XCode for MacOSX). 
    Then you can follow the procedure below:

    1) Download the current version of the software (pda-XXX.tar.gz where 
       XXX is the current version number) from its 
       web page <http://www.cibiv.at/software/pda>.
    2) Extract the files (e.g., with tar xvzf 'pda-XXX.tar.gz' under Unix)
       This should create a directory pda-XXX.
    3) Change into this directory.
    4) To compile the program, type the following:

         ./configure

       This should configure the package for the build. You might also 
       want to refer to the INSTALL file for more (general) details.

         make

       This compiles and builds the executable 'pda'
       (or 'pda.exe' on Windows systems) to be found in the 'src'
       directory.  This executable can copied to your system's search path
       such that it is found by your system or it can be installed
       to the default destination (e.g., /usr/local/bin on UNIX/Linux) using 

         make install

    If you encounter problems, please ask your local administrator for help.


*****************************************************************************
*    This program is distributed in the hope that it will be useful, but    *
*    WITHOUT ANY WARRANTY; without even the implied warranty of             *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU       *
*    General Public License for more details.                               *
*****************************************************************************
