1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
/**********************************************************************
* File: buildtree.h
* Author: Kevin Howe
* Copyright (C) Genome Research Limited, 2002-
*-------------------------------------------------------------------
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*-------------------------------------------------------------------
* NOTES:
* Contains functions for building trees from distance matrices
* (and vice versa)
**********************************************************************/
#ifndef _BUILDTREE
#define _BUILDTREE
#include <float.h>
#include "util.h"
#include "tree.h"
#include "cluster.h"
/******************* structure definitions ****************************/
/********************** function prototypes ***************************/
/**********************************************************************
FUNCTION: export_distances_buildtree
DESCRIPTION:
Returns the distance matrix induced from the given tree, i.e. by summing
the branch paths between two nodes to obtain their distance
ARGS:
A Tree
A DistanceMatrix
RETURNS:
NOTES:
This function does not create the memory for the distance matrix, it
merely fills in the given matrix
**********************************************************************/
void export_distances_buildtree( struct Tree *, struct DistanceMatrix *);
/**********************************************************************
FUNCTION: find_path_buildtree
DESCRIPTION:
Given a leaf node, recursively calculates the branch-length distance
from the node to all other leaves in the tree, and places it in the
appropriate part of the DistanceMatrix
ARGS:
unsigned int (the node number from which we are finding all distances)
Tnode (the current node under consideration)
DistanceMatrix
Boolean array (to store which nodes have already been considered)
unsigned int (the size of this boolean array)
RETURNS:
NOTES:
**********************************************************************/
void find_path_buildtree( unsigned int,
struct Tnode *,
struct DistanceMatrix *,
Distance,
unsigned int *);
/**********************************************************************
FUNCTION: leaf_find_buildtree
DESCRIPTION:
Finds the leaf nodes descended from the given interior node, and
calculates the distance from these nodes to all other nodes, by
way of another function call
ARGS:
Tnode
DistanceMatrix
Boolean array (to store which nodes have already been considered)
unsigned int (the size of this boolean array)
RETURNS:
NOTES:
**********************************************************************/
void leaf_find_buildtree( struct Tnode *,
struct DistanceMatrix *,
unsigned int *,
unsigned int);
/**********************************************************************
FUNCTION: neighbour_joining_buildtree
DESCRIPTION:
Returns a phylogenetic tree of the sequences in the
given alignment, using Saitou and Nei's neighbour-joining
algorithm
ARGS:
A ClusterGroup pointer (cluster.h)
Boolean, for whether to calc information needed for later bootstrapping
RETURNS:
A Tree (trees.h)
NOTES: The function allocates all the memory necessary for the tree.
The caller should call free_tree (tree.h) to free this memory when
the tree is no longer needed
**********************************************************************/
struct Tree *neighbour_joining_buildtree( struct ClusterGroup *,
unsigned int);
/**********************************************************************
FUNCTION: UPGMA_buildtree
DESCRIPTION:
Returns a phylogenetic tree of the sequences in the
given alignment, using the Unweighted Pair-Group method based on
Arithmentic Averages (UPGMA)
ARGS:
A ClusterGroup pointer (cluster.h)
Boolean, for whether to calc information needed for later bootstrapping
RETURNS:
struct Tree (trees.h)
NOTES: The function allocates all the memory necessary for the tree.
The caller should call free_Tnode (tree.h) to free this memory when
the tree is no longer needed
This algorithm produces a rooted tree; hence the returned Tree
will have the root in child[0]; child[1] and child[2] (used to
represent the trichotomy of unrooted trees) will be NULL
**********************************************************************/
struct Tree *UPGMA_buildtree( struct ClusterGroup *, unsigned int);
#endif
|
