NCBI C++ ToolKit
tree.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef ALGO_COBALT___TREE__HPP
2 #define ALGO_COBALT___TREE__HPP
3 
4 /* $Id: tree.hpp 45627 2010-05-03 17:44:40Z boratyng $
5 * ===========================================================================
6 *
7 * PUBLIC DOMAIN NOTICE
8 * National Center for Biotechnology Information
9 *
10 * This software/database is a "United States Government Work" under the
11 * terms of the United States Copyright Act. It was written as part of
12 * the author's offical duties as a United States Government employee and
13 * thus cannot be copyrighted. This software/database is freely available
14 * to the public for use. The National Library of Medicine and the U.S.
15 * Government have not placed any restriction on its use or reproduction.
16 *
17 * Although all reasonable efforts have been taken to ensure the accuracy
18 * and reliability of the software and data, the NLM and the U.S.
19 * Government do not and cannot warrant the performance or results that
20 * may be obtained by using this software or data. The NLM and the U.S.
21 * Government disclaim all warranties, express or implied, including
22 * warranties of performance, merchantability or fitness for any particular
23 * purpose.
24 *
25 * Please cite the author in any work or product based on this material.
26 *
27 * ===========================================================================*/
28 
29 /*****************************************************************************
30 
31 File name: tree.hpp
32 
33 Author: Jason Papadopoulos
34 
35 Contents: Interface for CTree class
36 
37 ******************************************************************************/
38 
39 /// @file tree.hpp
40 /// Interface for CTree class
41 
43 
44 #include <algo/cobalt/base.hpp>
45 #include <algo/cobalt/seq.hpp>
46 #include <algo/cobalt/hitlist.hpp>
47 
49 BEGIN_SCOPE(cobalt)
50 
51 /// A wrapper for controlling access to the phylogenetic
52 /// tree generated by CDistMethods
54 {
55 
56 public:
57 
58  /// Structure for listing tree edges
59  struct STreeEdge {
60  const TPhyTreeNode *node; ///< pointer to this edge in the tree
61  double distance; ///< length of this edge
62 
63  /// Initialize an edge
64  /// @param n The edge [in]
65  /// @param d length of the edge [in]
66  ///
67  STreeEdge(const TPhyTreeNode *n, double d)
68  : node(n), distance(d) {}
69  };
70 
71  /// Structure for listing tree leaves
72  struct STreeLeaf {
73  int query_idx; ///< Ordinal ID of the sequence at leaf
74  double distance; ///< Length of path to this leaf
75 
76  /// Initialize an edge
77  /// @param q Ordinal ID of the sequence at this leaf [in]
78  /// @param d Length of path from the leaf to some
79  /// internal node in the tree [in]
80  ///
81  STreeLeaf(int q, double d)
82  : query_idx(q), distance(d) {}
83  };
84 
85  /// Make an empty tree
86  ///
87  CTree() { m_Tree = 0; }
88 
89  /// Constructor: build a tree
90  /// @param distances Matrix of pairwise distances from
91  /// which the tree will be derived [in]
92  /// @param use_fastme If true, use the FASTME algorithm for
93  /// tree construction; else use neighbor-joining
94  ///
95  CTree(const CDistMethods::TMatrix& distances,
96  bool use_fastme = false)
97  {
98  m_Tree = 0;
99  ComputeTree(distances, use_fastme);
100  }
101 
102  /// Destructor (deletes generated tree)
103  ///
104  ~CTree() { delete m_Tree; }
105 
106  /// Compute a new tree
107  /// @param distances Matrix of pairwise distances from
108  /// which the tree will be derived [in]
109  /// @param use_fastme If true, use the FASTME algorithm for
110  /// tree construction; else use neighbor-joining
111  ///
112  void ComputeTree(const CDistMethods::TMatrix& distances,
113  bool use_fastme = false);
114 
115  /// Access the current tree.
116  /// All trees generated by this class are in the same format:
117  /// the tree is strictly binary, each leaf is associated with
118  /// a row of the underlying distance matrix, and the root does
119  /// not refer to any sequence. The root will almost always have
120  /// one leaf and an internal edge of length zero as children; the
121  /// zero length edge connects to the rest of the tree
122  /// @return The current tree
123  ///
124  const TPhyTreeNode * GetTree() const { return m_Tree; }
125 
126  /// Access the current tree.
127  /// @return The current tree
128  ///
129  TPhyTreeNode* GetTree() { return m_Tree; }
130 
131  /// Set tree
132  /// @param tree Pointer to tree root [in]
133  ///
134  void SetTree(TPhyTreeNode* tree) {m_Tree = tree;}
135 
136  /// Get the current tree and release ownership
137  /// @return The current tree
138  ///
140  {TPhyTreeNode* result = m_Tree; m_Tree = NULL; return result;}
141 
142 
143  /// Traverse a tree below a given starting point, listing
144  /// all leaves encountered along the way. The length of the
145  /// path from the root to each leaf is also computed
146  /// @param node The root of the tree to traverse [in]
147  /// @param node_list List of leaves encountered [out]
148  /// @param curr_dist Bias to add to all computed distances [in]
149  ///
150  static void ListTreeLeaves(const TPhyTreeNode *node,
151  vector<STreeLeaf>& node_list,
152  double curr_dist = 0);
153 
154  /// Traverse a tree below a given starting point, listing
155  /// all edges encountered along the way. The length of each
156  /// edge is also saved
157  /// @param node The root of the tree to traverse [in]
158  /// @param node_list List of edges encountered [out]
159  /// @param max_id If non-negative, tree is not traversed below nodes with
160  /// id greater or equal to max_id [in]
161  ///
162  static void ListTreeEdges(const TPhyTreeNode *node,
163  vector<STreeEdge>& edge_list,
164  int max_id = -1);
165 
166  /// Debug routine to recursively print out a tree
167  /// @param node Root of tree [in]
168  /// @param level Internal variable (leave as zero) [in]
169  ///
170  static void PrintTree(const TPhyTreeNode *node,
171  int level = 0);
172 
173 private:
175 };
176 
177 END_SCOPE(cobalt)
179 
180 #endif // ALGO_COBALT___TREE__HPP
Definitions used by all COBALT aligner components.
definition of a Culling tree
Definition: ncbi_tree.hpp:100
A wrapper for controlling access to the phylogenetic tree generated by CDistMethods.
Definition: tree.hpp:54
void SetTree(TPhyTreeNode *tree)
Set tree.
Definition: tree.hpp:134
~CTree()
Destructor (deletes generated tree)
Definition: tree.hpp:104
CTree(const CDistMethods::TMatrix &distances, bool use_fastme=false)
Constructor: build a tree.
Definition: tree.hpp:95
TPhyTreeNode * GetTree()
Access the current tree.
Definition: tree.hpp:129
const TPhyTreeNode * GetTree() const
Access the current tree.
Definition: tree.hpp:124
TPhyTreeNode * m_Tree
Definition: tree.hpp:174
CTree()
Make an empty tree.
Definition: tree.hpp:87
TPhyTreeNode * ReleaseTree()
Get the current tree and release ownership.
Definition: tree.hpp:139
#define NULL
Definition: ncbistd.hpp:225
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define END_SCOPE(ns)
End the previously defined scope.
Definition: ncbistl.hpp:75
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
#define BEGIN_SCOPE(ns)
Define a new scope.
Definition: ncbistl.hpp:72
#define NCBI_COBALT_EXPORT
Definition: ncbi_export.h:977
Interface for CHitList class.
yy_size_t n
Interface for CSequence class.
Structure for listing tree edges.
Definition: tree.hpp:59
double distance
length of this edge
Definition: tree.hpp:61
STreeEdge(const TPhyTreeNode *n, double d)
Initialize an edge.
Definition: tree.hpp:67
const TPhyTreeNode * node
pointer to this edge in the tree
Definition: tree.hpp:60
Structure for listing tree leaves.
Definition: tree.hpp:72
double distance
Length of path to this leaf.
Definition: tree.hpp:74
int query_idx
Ordinal ID of the sequence at leaf.
Definition: tree.hpp:73
STreeLeaf(int q, double d)
Initialize an edge.
Definition: tree.hpp:81
else result
Definition: token2.c:20
Modified on Wed Feb 28 07:14:27 2024 by modify_doxy.py rev. 669887