Debian Codegraph @

README

raw
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