tree.hpp

Go to the documentation of this file.

Go to the SVN repository for this file.

#ifndef ALGO_COBALT___TREE__HPP
#define ALGO_COBALT___TREE__HPP
 
/* $Id: tree.hpp 45627 2010-05-03 17:44:40Z boratyng $
* ===========================================================================
*
*                            PUBLIC DOMAIN NOTICE
*               National Center for Biotechnology Information
*
*  This software/database is a "United States Government Work" under the
*  terms of the United States Copyright Act.  It was written as part of
*  the author's offical duties as a United States Government employee and
*  thus cannot be copyrighted.  This software/database is freely available
*  to the public for use. The National Library of Medicine and the U.S.
*  Government have not placed any restriction on its use or reproduction.
*
*  Although all reasonable efforts have been taken to ensure the accuracy
*  and reliability of the software and data, the NLM and the U.S.
*  Government do not and cannot warrant the performance or results that
*  may be obtained by using this software or data. The NLM and the U.S.
*  Government disclaim all warranties, express or implied, including
*  warranties of performance, merchantability or fitness for any particular
*  purpose.
*
*  Please cite the author in any work or product based on this material.
*
* ===========================================================================*/
 
/*****************************************************************************
 
File name: tree.hpp
 
Author: Jason Papadopoulos
 
Contents: Interface for CTree class
 
******************************************************************************/
 
/// @file tree.hpp
/// Interface for CTree class
 
#include <algo/phy_tree/dist_methods.hpp>
 
#include <algo/cobalt/base.hpp>
#include <algo/cobalt/seq.hpp>
#include <algo/cobalt/hitlist.hpp>
 
BEGIN_NCBI_SCOPE
BEGIN_SCOPE(cobalt)
 
/// A wrapper for controlling access to the phylogenetic
/// tree generated by CDistMethods
class NCBI_COBALT_EXPORT CTree
{
 
public:
 
    /// Structure for listing tree edges
    struct STreeEdge {
        const TPhyTreeNode *node;    ///< pointer to this edge in the tree
        double distance;             ///< length of this edge
 
        /// Initialize an edge
        /// @param n The edge [in]
        /// @param d length of the edge [in]
        ///
        STreeEdge(const TPhyTreeNode *n, double d)
            : node(n), distance(d) {}
    };
    
    /// Structure for listing tree leaves
    struct STreeLeaf {
        int query_idx;            ///< Ordinal ID of the sequence at leaf
        double distance;          ///< Length of path to this leaf
 
        /// Initialize an edge
        /// @param q Ordinal ID of the sequence at this leaf [in]
        /// @param d Length of path from the leaf to some 
        ///          internal node in the tree [in]
        ///
        STreeLeaf(int q, double d)
            : query_idx(q), distance(d) {}
    };
 
    /// Make an empty tree
    ///
    CTree() { m_Tree = 0; }
 
    /// Constructor: build a tree
    /// @param distances Matrix of pairwise distances from
    ///                  which the tree will be derived [in]
    /// @param use_fastme If true, use the FASTME algorithm for
    ///                  tree construction; else use neighbor-joining
    ///
    CTree(const CDistMethods::TMatrix& distances,
          bool use_fastme = false)
    {
        m_Tree = 0;
        ComputeTree(distances, use_fastme);
    }
 
    /// Destructor (deletes generated tree)
    ///
    ~CTree() { delete m_Tree; }
 
    /// Compute a new tree
    /// @param distances Matrix of pairwise distances from
    ///                  which the tree will be derived [in]
    /// @param use_fastme If true, use the FASTME algorithm for
    ///                  tree construction; else use neighbor-joining
    ///
    void ComputeTree(const CDistMethods::TMatrix& distances,
                     bool use_fastme = false);
 
    /// Access the current tree.
    /// All trees generated by this class are in the same format:
    /// the tree is strictly binary, each leaf is associated with
    /// a row of the underlying distance matrix, and the root does
    /// not refer to any sequence. The root will almost always have
    /// one leaf and an internal edge of length zero as children; the
    /// zero length edge connects to the rest of the tree
    /// @return The current tree
    ///
    const TPhyTreeNode * GetTree() const { return m_Tree; }
 
    /// Access the current tree.
    /// @return The current tree
    ///
    TPhyTreeNode* GetTree() { return m_Tree; }
 
    /// Set tree
    /// @param tree Pointer to tree root [in]
    ///
    void SetTree(TPhyTreeNode* tree) {m_Tree = tree;}
 
    /// Get the current tree and release ownership
    /// @return The current tree
    ///
    TPhyTreeNode* ReleaseTree()
    {TPhyTreeNode* result = m_Tree; m_Tree = NULL; return result;}
 
 
    /// Traverse a tree below a given starting point, listing
    /// all leaves encountered along the way. The length of the
    /// path from the root to each leaf is also computed
    /// @param node The root of the tree to traverse [in]
    /// @param node_list List of leaves encountered [out]
    /// @param curr_dist Bias to add to all computed distances [in]
    ///
    static void ListTreeLeaves(const TPhyTreeNode *node,
                               vector<STreeLeaf>& node_list,
                               double curr_dist = 0);
 
    /// Traverse a tree below a given starting point, listing
    /// all edges encountered along the way. The length of each
    /// edge is also saved
    /// @param node The root of the tree to traverse [in]
    /// @param node_list List of edges encountered [out]
    /// @param max_id If non-negative, tree is not traversed below nodes with
    /// id greater or equal to max_id [in]
    ///
    static void ListTreeEdges(const TPhyTreeNode *node,
                              vector<STreeEdge>& edge_list,
                              int max_id = -1);
 
    /// Debug routine to recursively print out a tree
    /// @param node Root of tree [in]
    /// @param level Internal variable (leave as zero) [in]
    ///
    static void PrintTree(const TPhyTreeNode *node,
                          int level = 0);
 
private:
    TPhyTreeNode *m_Tree;
};
 
END_SCOPE(cobalt)
END_NCBI_SCOPE
 
#endif // ALGO_COBALT___TREE__HPP