| 1 |
$Id: README,v 1.3 2006/09/01 04:55:39 sheneman Exp $ |
| 2 |
|
| 3 |
****************************************************************************** |
| 4 |
|
| 5 |
Clearcut :: Relaxed Neighbor Joining |
| 6 |
|
| 7 |
(Version 1.0.9, Feb. 2009) |
| 8 |
|
| 9 |
****************************************************************************** |
| 10 |
|
| 11 |
INTRODUCTION: |
| 12 |
------------- |
| 13 |
|
| 14 |
Clearcut is the reference implementation for the Relaxed Neighbor Joining (RNJ) |
| 15 |
algorithm by J. Evans, L. Sheneman, and J. Foster from the Initiative |
| 16 |
for Bioinformatics and Evolutionary Studies (IBEST) at the University of |
| 17 |
Idaho. |
| 18 |
|
| 19 |
Details of RNJ are published here: |
| 20 |
|
| 21 |
Evans, J., L. Sheneman, and J.A. Foster (2006) Relaxed Neighbor-Joining: |
| 22 |
A Fast Distance-Based Phylogenetic Tree Construction Method, |
| 23 |
J. Mol. Evol., 62, 785-792 |
| 24 |
|
| 25 |
Relaxed Neighbor-Joining (RNJ) is a fast approximation to the |
| 26 |
Neighbor Joining algorithm originally described in: |
| 27 |
|
| 28 |
Saitou, N. and M. Nei (1987), The Neighbor-Joining method: A new method |
| 29 |
for reconstructing phylogenetic trees., Mol. Biol. Evol. 4:406-425 |
| 30 |
|
| 31 |
and revised in: |
| 32 |
|
| 33 |
Studier, J. and K. Keppler (1988), A note on the neighbor-joining |
| 34 |
algorithm of Saitou and Nei., Mol. Biol. Evol. 5:729-731 |
| 35 |
|
| 36 |
|
| 37 |
Whereas traditional Neighbor-Joining has a cubic time complexity with |
| 38 |
respect to the number of input sequences, Relaxed Neighbor-Joining has |
| 39 |
a drastically reduced, sub-cubic time complexity for the average case. |
| 40 |
In addition to being significantly (and asymptotically) |
| 41 |
more efficient, Relaxed Neighbor-Joining shares some nice theoretical |
| 42 |
properties with Traditional Neighbor-Joining. In particular, if distances |
| 43 |
are truly additive (self-consistent), RNJ will reconstruct the true tree |
| 44 |
that is consistent with those additive distances. |
| 45 |
|
| 46 |
For non-additive distances, RNJ will sample the space of similar trees |
| 47 |
more thoroughly than traditional NJ by greedily joining nodes which |
| 48 |
represent a locally (as opposed to globally) minimum distance between |
| 49 |
nodes. This results in sampling more trees than it is possible to explore |
| 50 |
through NJ alone. Additionally, it has been empirically shown that |
| 51 |
for non-additive distances, RNJ is capable of reconstructing trees which |
| 52 |
are nearly qualitatively indistinct from trees built via the conventional |
| 53 |
Neighbor-Joining algorithm. |
| 54 |
|
| 55 |
****************************************************************************** |
| 56 |
|
| 57 |
|
| 58 |
INSTALLING CLEARCUT: |
| 59 |
-------------------- |
| 60 |
|
| 61 |
Clearcut was developed and tested primarily under Redhat Linux 7.2 and |
| 62 |
Redhat Enterprise Linux 3 on the Pentium 3 and Pentium 4 architectures. |
| 63 |
However, Clearcut should compile and run easily on other UNIX and |
| 64 |
UNIX-like operating systems. For example, clearcut builds cleanly on |
| 65 |
the Sun Solaris 9 and Apple OS X platforms. |
| 66 |
|
| 67 |
Good compiler optimization can result in an approximate 2X overall speedup |
| 68 |
for Clearcut. Compiler optimizations for GCC under Linux on the |
| 69 |
Pentium 4 architecture have been thoroughly explored. The Makefile |
| 70 |
included in this distribution has several possible sets of compiler |
| 71 |
flags available. Uncomment the appropriate set of compiler flags |
| 72 |
for your particular architecture and compiler combination. The |
| 73 |
default CFLAGS is set to basic level 3 optimization with gcc, but significant |
| 74 |
additional compiler optimizations are most likely available/desirable. |
| 75 |
|
| 76 |
|
| 77 |
To build Clearcut: |
| 78 |
|
| 79 |
+ Unzip and extract the distribution. |
| 80 |
+ Edit "Makefile" and select the appropriate optimization flags |
| 81 |
+ Type "make" to compile and link clearcut |
| 82 |
+ Type "make install" to install clearcut on your system |
| 83 |
|
| 84 |
|
| 85 |
****************************************************************************** |
| 86 |
|
| 87 |
|
| 88 |
RUNNING CLEARCUT: |
| 89 |
----------------- |
| 90 |
|
| 91 |
Clearcut has a variety of possible command-line arguments. To see the |
| 92 |
available arguments, type: |
| 93 |
|
| 94 |
$> clearcut --help |
| 95 |
|
| 96 |
Clearcut is capable of reading either a pre-computed distance matrix in |
| 97 |
approximate PHYLIP format, or it can input an alignment in FASTA format. |
| 98 |
In addition to fully symmetric distance matrices, clearcut can parse |
| 99 |
upper and lower diagonal half-matrices. |
| 100 |
|
| 101 |
Clearcut can build a distance matrix from a Multiple Sequence Alignment (MSA) |
| 102 |
of either DNA or Protein sequences. When building a distance matrix, |
| 103 |
percent pairwise differences can be corrected for multiple hits using either |
| 104 |
the Jukes-Cantor or Kimura correction methods as described in: |
| 105 |
|
| 106 |
Kimura, M. (1980), A simple method for estimating evolutionary |
| 107 |
rates of base substitutions through comparative studies of |
| 108 |
nucleotide sequences. J. Mol. Evol., 16, 111-120 |
| 109 |
|
| 110 |
Kimura, M. (1983), The Neutral Theory of Molecular Evolution. |
| 111 |
p. 75., Cambridge University Press, Cambridge, England |
| 112 |
|
| 113 |
Jukes, T.H. (1969), Evolution of protein molecules. In H.N. Munro (Ed.), |
| 114 |
Mammalian Protein Metabolism, Volume III, Chapter 24, pp. 21-132. |
| 115 |
New York: Academic Press |
| 116 |
|
| 117 |
|
| 118 |
By default, Clearcut will perform joins in a random fashion in order to |
| 119 |
minimize systematic algorithmic bias. This option can be disabled using |
| 120 |
the --norandom runtime option. |
| 121 |
|
| 122 |
By default, Clearcut uses Relaxed Neighbor-Joining, although Traditional |
| 123 |
Neighbor-Joining can be invoked with the --neighbor runtime option. |
| 124 |
|
| 125 |
|
| 126 |
****************************************************************************** |
| 127 |
|
| 128 |
|
| 129 |
AUTHOR/MAINTAINER: |
| 130 |
------------------ |
| 131 |
|
| 132 |
|
| 133 |
Clearcut is maintained by: Luke Sheneman |
| 134 |
[email protected] |
| 135 |
https://github.com/sheneman/clearcut |
| 136 |
|
| 137 |
|
| 138 |
Please contact the maintainer with questions, bug reports, and feedback!! |
| 139 |
|
| 140 |
|
| 141 |
|
| 142 |
****************************************************************************** |
| 143 |
|
| 144 |
LICENSE: |
| 145 |
-------- |
| 146 |
|
| 147 |
Clearcut is distributed under the BSD license, which is described in |
| 148 |
the LICENSE file that is bundled with this program. |
| 149 |
|
| 150 |
****************************************************************************** |
| 151 |
|
| 152 |
|
| 153 |
|
| 154 |
|