PTreeGenerator  1.0
Simple phylogenetic tree generation from multiple sequence alignment.
 All Classes Namespaces Files Functions Variables
Public Member Functions | Private Attributes | List of all members
ptreegen.neighbor_joining.NeighborJoining Class Reference

Contains an implementation of the Neighbor-Joining algorithm. More...

Public Member Functions

def __init__
 The constructor just saves the data for the execution.
def tree
 Neighbor-Joining implementation.

Private Attributes

 _alignment
 multiple sequence alignment
 _names
 taxa identification strings
 _distMatrix
 the distance matrix in more or less arbitrary form

Detailed Description

Contains an implementation of the Neighbor-Joining algorithm.

The computed tree is stored as an internal member NeighborJoining::tree.

Definition at line 14 of file neighbor_joining.py.

Constructor & Destructor Documentation

def ptreegen.neighbor_joining.NeighborJoining.__init__ (   self,
  distMatrtix,
  alignment = None,
  names = None 
)

The constructor just saves the data for the execution.

Parameters
distMatrtixthe distance matrix
alignmentshould be specified when the names parameter is not present
namesthe names of the taxa in the distance matrix

Definition at line 22 of file neighbor_joining.py.

22 
23  def __init__(self, distMatrtix, alignment=None, names=None):
24  self._alignment = alignment
25  self._names = names
26  if self._alignment:
27  self._distMatrix = DistanceMatrix(distMatrtix, [x.id for x in self._alignment])
28  elif self._names:
29  self._distMatrix = DistanceMatrix(distMatrtix, self._names)
30  else:
31  raise RuntimeError("You must pass either an alignment or a list of names.")

Member Function Documentation

def ptreegen.neighbor_joining.NeighborJoining.tree (   self)

Neighbor-Joining implementation.

Returns
constructed tree with edges weighted by distances

Definition at line 37 of file neighbor_joining.py.

Referenced by ptreegen.parsimony.LargeParsimony.cost().

37 
38  def tree(self):
39  L = self._distMatrix.columnNames
40  tree = Tree()
41  tree.name = "root"
42  tree.dist = 0
43  for seq in L:
44  tree.add_child(name=seq, dist=0)
45 
46  iter_count = 1
47  while len(L) > 2:
48  nearest_nbs = self._distMatrix.getNearestNeigbors()
49  node_i = tree.search_nodes(name=nearest_nbs[0])[0]
50  node_j = tree.search_nodes(name=nearest_nbs[1])[0]
51  L.remove(nearest_nbs[0])
52  L.remove(nearest_nbs[1])
53 
54  node_k = Tree()
55  node_k.dist = 0
56  node_k.name = "X" + str(iter_count)
57  d_ij = self._distMatrix.getDistance(node_i.name, node_j.name)
58  assert d_ij > 0
59  d_ik = 0.5 * d_ij + 0.5 * (self._distMatrix.getSeparation(node_i.name) - self._distMatrix.getSeparation(node_j.name))
60  d_jk = 0.5 * d_ij + 0.5 * (self._distMatrix.getSeparation(node_j.name) - self._distMatrix.getSeparation(node_i.name))
61 
62  tree.remove_child(node_i)
63  tree.remove_child(node_j)
64  node_k.add_child(node_i, dist=d_ik)
65  node_k.add_child(node_j, dist=d_jk)
66  tree.add_child(node_k)
67 
68  d_km = []
69  for node_m in L:
70  d_km.append(0.5 * (self._distMatrix.getDistance(node_i.name, node_m) + self._distMatrix.getDistance(node_j.name, node_m) - d_ij) )
71  assert d_km > 0
72 
73  self._distMatrix.removeData((node_i.name, node_j.name))
74  self._distMatrix.appendData(d_km, node_k.name)
75 
76  iter_count+=1
77  L = self._distMatrix.columnNames
78 
79  last_nodes = tree.get_children()
80  d_ij = self._distMatrix.getDistance(last_nodes[0].name, last_nodes[1].name)
81  leaf = None
82  new_root = None
83  for node in last_nodes:
84  if node.is_leaf():
85  node.dist = d_ij
86  leaf = node.detach()
87  else:
88  new_root = node.detach()
89  if not leaf:
90  leaf = last_nodes[0]
91  leaf.dist = d_ij
92  new_root.add_child(leaf)
93 
94  return new_root

Member Data Documentation

ptreegen.neighbor_joining.NeighborJoining._alignment
private

multiple sequence alignment

Definition at line 23 of file neighbor_joining.py.

Referenced by ptreegen.parsimony.LargeParsimony.cost(), and ptreegen.parsimony.LargeParsimony.getOptimalQuartets().

ptreegen.neighbor_joining.NeighborJoining._distMatrix
private

the distance matrix in more or less arbitrary form

Definition at line 26 of file neighbor_joining.py.

ptreegen.neighbor_joining.NeighborJoining._names
private

taxa identification strings

Definition at line 24 of file neighbor_joining.py.

The documentation for this class was generated from the following file:
Generated on Thu Feb 12 2015 00:08:00 for PTreeGenerator by   doxygen 1.8.1.2