jade::basic_neighbor_joining< TValue > Class Template Reference

A template for a class that implements the neighbor joining algorithm. More...

#include <jade.neighbor_joining.hpp>

Collaboration diagram for jade::basic_neighbor_joining< TValue >:

Public Types
typedef TValue	value_type
	The value type. More...
typedef basic_matrix< value_type >	matrix_type
	The matrix type. More...

Public Member Functions
	basic_neighbor_joining (const matrix_type &distances)
	Initializes a new instance of the class. More...
std::string	str () const
void	write (std::ostream &out) const
	Writes the constructed tree in Newick format to the specified output stream. More...

Detailed Description

template<typename TValue>
class jade::basic_neighbor_joining< TValue >

A template for a class that implements the neighbor joining algorithm.

Definition at line 18 of file jade.neighbor_joining.hpp.

Member Typedef Documentation

matrix_type

template<typename TValue >

typedef basic_matrix<value_type> jade::basic_neighbor_joining< TValue >::matrix_type

The matrix type.

Definition at line 25 of file jade.neighbor_joining.hpp.

value_type

template<typename TValue >

typedef TValue jade::basic_neighbor_joining< TValue >::value_type

The value type.

Definition at line 22 of file jade.neighbor_joining.hpp.

Constructor & Destructor Documentation

basic_neighbor_joining()

template<typename TValue >

jade::basic_neighbor_joining< TValue >::basic_neighbor_joining ( const matrix_type &  distances )

inlineexplicit

Initializes a new instance of the class.

Parameters

distances

The distance matrix.

Definition at line 30 of file jade.neighbor_joining.hpp.

            : _children ()
            , _lengths  ()
            , _names    ()
            , _root     (invalid_id)
        {
            //
            // Allow empty matrices even though no tree will be produced from
            // the write method.
            //
            if (distances.is_empty())
                return;
 
            //
            // Allow just one node even though the tree produced from the write
            // method will consist on only the node name ("0").
            //
            assert(distances.is_square());
            auto n = distances.get_height();
            id_type next_id = 0;
            if (n == 1)
            {
                _root = _add_leaf(next_id);
                return;
            }
 
            //
            // Prepare a list of ids for the initial set of nodes.
            //
            typedef std::vector<id_type> vector_type;
            vector_type x;
            for (size_t i = 0; i < n; i++)
                x.push_back(_add_leaf(next_id));
 
            //
            // Prepare the distance matrix that will be reduced by the
            // algorithm.
            //
            matrix_type d (distances);
 
            //
            // Loop until there are only two nodes remaining in the distance
            // matrix.
            //
            while (n > 2)
            {
                //
                // Find the minimum Q value in the matrix, and use it to find
                // the two nodes that will be joined. Join them by creating a
                // new parent node.
                //
                const q_data  q  (d);
                const id_type id (next_id++);
                _add_parent(id, x[q.i], q.d_ik);
                _add_parent(id, x[q.j], q.d_jk);
 
                //
                // Prepare the new, reduced distance matrix as well as the
                // corresponding id vector.
                //
                matrix_type dd (n - 1, n - 1);
                vector_type xx { id };
                for (size_t r = 0, rr = 1; r < n; r++)
                {
                    if (r == q.i || r == q.j)
                        continue;
                    xx.push_back(x[r]);
                    dd(rr, 0) = value_type(0.5) *
                        (d(r, q.i) + d(r, q.j) - q.d_ij);
                    for (size_t c = 0, cc = 1; c < r; c++)
                        if (c != q.i && c != q.j)
                            dd(rr, cc++) = d(r, c);
                    rr++;
                }
 
                //
                // Copy the lower triangle to the upper triangle so the data
                // in the next Q matrix matches the expected values.
                //
                dd.copy_lower_to_upper();
 
                d.swap(dd);
                x.swap(xx);
                n--;
            }
 
            //
            // Connect the last two nodes; note the loop above places new nodes
            // at index zero, so here it is known that the leaf node must be at
            // index 1, and so the root note must be at index 0.
            //
            _root = x[0];
            _add_parent(_root, x[1], d(1, 0));
        }

Here is the call graph for this function:

Member Function Documentation

str()

template<typename TValue >

std::string jade::basic_neighbor_joining< TValue >::str ( ) const

inline

Returns

A string representation of this class.

Definition at line 129 of file jade.neighbor_joining.hpp.

        {
            std::ostringstream out;
            write(out);
            return out.str();
        }

Here is the call graph for this function:

write()

template<typename TValue >

void jade::basic_neighbor_joining< TValue >::write ( std::ostream &  out ) const

inline

Writes the constructed tree in Newick format to the specified output stream.

Parameters

out	The output stream.

Definition at line 140 of file jade.neighbor_joining.hpp.

        {
            if (_root != invalid_id)
            {
                _write(out, _root);
                out << ';';
            }
        }

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• jade.neighbor_joining.hpp