Back to index

python-biopython  1.60
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes
Bio.Nexus.Trees.Tree Class Reference
Inheritance diagram for Bio.Nexus.Trees.Tree:
Inheritance graph
[legend]
Collaboration diagram for Bio.Nexus.Trees.Tree:
Collaboration graph
[legend]

List of all members.

Public Member Functions

def __init__
 NOTE: Tree should store its data class in something like self.dataclass=data, so that nodes that are generated have easy access to the data class Some routines use automatically NodeData, this needs to be more concise.
def node
def split
def search_taxon
def prune
def get_taxa
def get_terminals
def is_terminal
def is_internal
def is_preterminal
def count_terminals
def collapse_genera
def sum_branchlength
def set_subtree
def is_identical
def is_compatible
def common_ancestor
def distance
def is_monophyletic
def is_bifurcating
def branchlength2support
def convert_absolute_support
def has_support
def randomize
def display
def to_string
def __str__
def unroot
def root_with_outgroup
def merge_with_support
def all_ids
def add
def collapse
def kill
def unlink
def link
def is_parent_of
def trace

Public Attributes

 dataclass
 max_support
 weight
 rooted
 name
 root
 support_as_branchlengths
 branchlengths_only
 ignore_comments
 plain
 unrooted
 chain
 id

Private Member Functions

def _parse
def _add_subtree
def _add_nodedata
def _get_values
def _walk

Private Attributes

 __values_are_support

Detailed Description

Represents a tree using a chain of nodes with on predecessor (=ancestor)
and multiple successors (=subclades).

Definition at line 33 of file Trees.py.


Constructor & Destructor Documentation

def Bio.Nexus.Trees.Tree.__init__ (   self,
  tree = None,
  weight = 1.0,
  rooted = False,
  name = '',
  data = NodeData,
  values_are_support = False,
  max_support = 1.0 
)

NOTE: Tree should store its data class in something like self.dataclass=data, so that nodes that are generated have easy access to the data class Some routines use automatically NodeData, this needs to be more concise.

Ntree(self,tree).

Definition at line 46 of file Trees.py.

00046 
00047     def __init__(self,tree=None,weight=1.0,rooted=False,name='',data=NodeData,values_are_support=False,max_support=1.0):
00048         """Ntree(self,tree)."""
00049         Nodes.Chain.__init__(self)
00050         self.dataclass=data
00051         self.__values_are_support=values_are_support
00052         self.max_support=max_support
00053         self.weight=weight
00054         self.rooted=rooted
00055         self.name=name
00056         root=Nodes.Node(data())
00057         self.root = self.add(root)
00058         if tree:    # use the tree we have
00059             # if Tree is called from outside Nexus parser, we need to get rid of linebreaks, etc
00060             tree=tree.strip().replace('\n','').replace('\r','')
00061             # there's discrepancy whether newick allows semicolons et the end
00062             tree=tree.rstrip(';')
00063             subtree_info, base_info = self._parse(tree)
00064             root.data = self._add_nodedata(root.data, [[], base_info])
00065             self._add_subtree(parent_id=root.id,tree=subtree_info)
        

Member Function Documentation

Short version of to_string(), gives plain tree

Definition at line 640 of file Trees.py.

00640 
00641     def __str__(self):
00642         """Short version of to_string(), gives plain tree"""
00643         return self.to_string(plain=True)
        

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree._add_nodedata (   self,
  nd,
  st 
) [private]
Add data to the node parsed from the comments, taxon and support.

Definition at line 123 of file Trees.py.

00123 
00124     def _add_nodedata(self, nd, st):
00125         """Add data to the node parsed from the comments, taxon and support.
00126         """
00127         if isinstance(st[1][-1],str) and st[1][-1].startswith(NODECOMMENT_START):
00128             nd.comment=st[1].pop(-1)
00129         # if the first element is a string, it's the subtree node taxon
00130         elif isinstance(st[1][0], str):
00131             nd.taxon = st[1][0]
00132             st[1] = st[1][1:]
00133         if len(st)>1:
00134             if len(st[1])>=2: # if there's two values, support comes first. Is that always so?
00135                 nd.support=st[1][0]
00136                 if st[1][1] is not None:
00137                     nd.branchlength=st[1][1]
00138             elif len(st[1])==1: # otherwise it could be real branchlengths or support as branchlengths
00139                 if not self.__values_are_support: # default
00140                     if st[1][0] is not None:
00141                         nd.branchlength=st[1][0]
00142                 else:
00143                     nd.support=st[1][0]
00144         return nd
    

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree._add_subtree (   self,
  parent_id = None,
  tree = None 
) [private]
Adds leaf or tree (in newick format) to a parent_id. (self,parent_id,tree).

Definition at line 107 of file Trees.py.

00107 
00108     def _add_subtree(self,parent_id=None,tree=None):
00109         """Adds leaf or tree (in newick format) to a parent_id. (self,parent_id,tree)."""
00110         if parent_id is None:
00111             raise TreeError('Need node_id to connect to.')
00112         for st in tree:
00113             nd=self.dataclass()
00114             nd = self._add_nodedata(nd, st)
00115             if type(st[0])==list: # it's a subtree
00116                 sn=Nodes.Node(nd)
00117                 self.add(sn,parent_id)
00118                 self._add_subtree(sn.id,st[0])
00119             else: # it's a leaf
00120                 nd.taxon=st[0]
00121                 leaf=Nodes.Node(nd)
00122                 self.add(leaf,parent_id)

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree._get_values (   self,
  text 
) [private]
Extracts values (support/branchlength) from xx[:yyy], xx.

Definition at line 145 of file Trees.py.

00145 
00146     def _get_values(self, text):
00147         """Extracts values (support/branchlength) from xx[:yyy], xx."""
00148        
00149         if text=='':
00150             return None
00151         nodecomment = None
00152         if NODECOMMENT_START in text: # if there's a [&....] comment, cut it out
00153             nc_start=text.find(NODECOMMENT_START)
00154             nc_end=text.find(NODECOMMENT_END)
00155             if nc_end==-1:
00156                 raise TreeError('Error in tree description: Found %s without matching %s' \
00157                                 % (NODECOMMENT_START, NODECOMMENT_END))
00158             nodecomment=text[nc_start:nc_end+1]
00159             text=text[:nc_start]+text[nc_end+1:]
00160 
00161         # pase out supports and branchlengths, with internal node taxa info
00162         values = []
00163         taxonomy = None
00164         for part in [t.strip() for t in text.split(":")]:
00165             if part:
00166                 try:
00167                     values.append(float(part))
00168                 except ValueError:
00169                     assert taxonomy is None, "Two string taxonomies?"
00170                     taxonomy = part
00171         if taxonomy:
00172             values.insert(0, taxonomy)
00173         if nodecomment:
00174             values.append(nodecomment)
00175         return values
   

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree._parse (   self,
  tree 
) [private]
Parses (a,b,c...)[[[xx]:]yy] into subcomponents and travels down recursively.

Definition at line 66 of file Trees.py.

00066 
00067     def _parse(self,tree):
00068         """Parses (a,b,c...)[[[xx]:]yy] into subcomponents and travels down recursively."""
00069         #Remove any leading/trailing white space - want any string starting
00070         #with " (..." should be recognised as a leaf, "(..."
00071         tree = tree.strip()
00072         if tree.count('(')!=tree.count(')'):
00073             raise TreeError('Parentheses do not match in (sub)tree: '+tree)
00074         if tree.count('(')==0: # a leaf
00075             #check if there's a colon, or a special comment, or both  after the taxon name
00076             nodecomment=tree.find(NODECOMMENT_START)
00077             colon=tree.find(':')
00078             if colon==-1 and nodecomment==-1: # none
00079                 return [tree,[None]]
00080             elif colon==-1 and nodecomment>-1: # only special comment
00081                 return [tree[:nodecomment],self._get_values(tree[nodecomment:])]
00082             elif colon>-1 and nodecomment==-1: # only numerical values
00083                 return [tree[:colon],self._get_values(tree[colon+1:])]
00084             elif colon < nodecomment: # taxon name ends at first colon or with special comment
00085                 return [tree[:colon],self._get_values(tree[colon+1:])]
00086             else:
00087                 return [tree[:nodecomment],self._get_values(tree[nodecomment:])]
00088         else:
00089             closing=tree.rfind(')')
00090             val=self._get_values(tree[closing+1:])
00091             if not val:
00092                 val=[None]
00093             subtrees=[]
00094             plevel=0
00095             prev=1
00096             for p in range(1,closing):
00097                 if tree[p]=='(':
00098                     plevel+=1
00099                 elif tree[p]==')':
00100                     plevel-=1
00101                 elif tree[p]==',' and plevel==0:
00102                     subtrees.append(tree[prev:p])
00103                     prev=p+1
00104             subtrees.append(tree[prev:closing])
00105             subclades=[self._parse(subtree) for subtree in subtrees]
00106             return [subclades,val]
    

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree._walk (   self,
  node = None 
) [private]
Return all node_ids downwards from a node.

Definition at line 176 of file Trees.py.

00176 
00177     def _walk(self,node=None):
00178         """Return all node_ids downwards from a node."""
00179         
00180         if node is None:
00181             node=self.root
00182         for n in self.node(node).succ:
00183             yield n
00184             for sn in self._walk(n):
00185                 yield sn

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.add (   self,
  node,
  prev = None 
) [inherited]
Attaches node to another: (self, node, prev).

Definition at line 40 of file Nodes.py.

00040 
00041     def add(self,node,prev=None):
00042         """Attaches node to another: (self, node, prev)."""
00043         if prev is not None and prev not in self.chain:
00044             raise ChainException('Unknown predecessor: '+str(prev))
00045         else:
00046             id=self._get_id()
00047             node.set_id(id)
00048             node.set_prev(prev)
00049             if prev is not None:
00050                 self.chain[prev].add_succ(id)
00051             self.chain[id]=node
00052         return id

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.all_ids (   self) [inherited]
Return a list of all node ids.

Definition at line 36 of file Nodes.py.

00036 
00037     def all_ids(self):
00038         """Return a list of all node ids."""
00039         return self.chain.keys()

Here is the caller graph for this function:

Move values stored in data.branchlength to data.support, and set branchlength to 0.0

This is necessary when support has been stored as branchlength (e.g. paup), and has thus
been read in as branchlength. 

Definition at line 458 of file Trees.py.

00458 
00459     def branchlength2support(self):
00460         """Move values stored in data.branchlength to data.support, and set branchlength to 0.0
00461 
00462         This is necessary when support has been stored as branchlength (e.g. paup), and has thus
00463         been read in as branchlength. 
00464         """
00465 
00466         for n in self.chain:
00467             self.node(n).data.support=self.node(n).data.branchlength
00468             self.node(n).data.branchlength=0.0

Here is the call graph for this function:

def Bio.Nexus.Nodes.Chain.collapse (   self,
  id 
) [inherited]
Deletes node from chain and relinks successors to predecessor: collapse(self, id).

Definition at line 53 of file Nodes.py.

00053 
00054     def collapse(self,id):
00055         """Deletes node from chain and relinks successors to predecessor: collapse(self, id)."""
00056         if id not in self.chain:
00057             raise ChainException('Unknown ID: '+str(id))
00058         prev_id=self.chain[id].get_prev()
00059         self.chain[prev_id].remove_succ(id)
00060         succ_ids=self.chain[id].get_succ()
00061         for i in succ_ids:
00062             self.chain[i].set_prev(prev_id)
00063         self.chain[prev_id].add_succ(succ_ids)
00064         node=self.chain[id]
00065         self.kill(id)
00066         return node

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.collapse_genera (   self,
  space_equals_underscore = True 
)
Collapses all subtrees which belong to the same genus (i.e share the same first word in their taxon name.

Definition at line 299 of file Trees.py.

00299 
00300     def collapse_genera(self,space_equals_underscore=True):
00301         """Collapses all subtrees which belong to the same genus (i.e share the same first word in their taxon name."""
00302 
00303         while True:
00304             for n in self._walk():
00305                 if self.is_terminal(n):
00306                     continue
00307                 taxa=self.get_taxa(n)
00308                 genera=[]
00309                 for t in taxa:
00310                     if space_equals_underscore:
00311                         t=t.replace(' ','_')
00312                     try:
00313                         genus=t.split('_',1)[0]
00314                     except:
00315                         genus='None'
00316                     if genus not in genera:
00317                         genera.append(genus)
00318                 if len(genera)==1:
00319                     self.node(n).data.taxon=genera[0]+' <collapsed>'
00320                     #now we kill all nodes downstream
00321                     nodes2kill=[kn for kn in self._walk(node=n)]
00322                     for kn in nodes2kill:
00323                         self.kill(kn)
00324                     self.node(n).succ=[]
00325                     break # break out of for loop because node list from _walk will be inconsistent
00326             else: # for loop exhausted: no genera to collapse left
00327                 break # while
00328 

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.common_ancestor (   self,
  node1,
  node2 
)
Return the common ancestor that connects two nodes.

node_id = common_ancestor(self,node1,node2)

Definition at line 402 of file Trees.py.

00402 
00403     def common_ancestor(self,node1,node2):
00404         """Return the common ancestor that connects two nodes.
00405         
00406         node_id = common_ancestor(self,node1,node2)
00407         """
00408         
00409         l1=[self.root]+self.trace(self.root,node1)
00410         l2=[self.root]+self.trace(self.root,node2)
00411         return [n for n in l1 if n in l2][-1]
00412 

Here is the call graph for this function:

Here is the caller graph for this function:

Convert absolute support (clade-count) to rel. frequencies.

Some software (e.g. PHYLIP consense) just calculate how often clades appear, instead of
calculating relative frequencies.

Definition at line 469 of file Trees.py.

00469 
00470     def convert_absolute_support(self,nrep):
00471         """Convert absolute support (clade-count) to rel. frequencies.
00472         
00473         Some software (e.g. PHYLIP consense) just calculate how often clades appear, instead of
00474         calculating relative frequencies."""
00475 
00476         for n in self._walk():
00477             if self.node(n).data.support:
00478                 self.node(n).data.support/=float(nrep)

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.count_terminals (   self,
  node = None 
)
Counts the number of terminal nodes that are attached to a node.

Definition at line 293 of file Trees.py.

00293 
00294     def count_terminals(self,node=None):
00295         """Counts the number of terminal nodes that are attached to a node."""
00296         if node is None:
00297             node=self.root
00298         return len([n for n in self._walk(node) if self.is_terminal(n)])

Here is the call graph for this function:

Quick and dirty lists of all nodes.

Definition at line 523 of file Trees.py.

00523 
00524     def display(self):
00525         """Quick and dirty lists of all nodes."""
00526         table=[('#','taxon','prev','succ','brlen','blen (sum)','support','comment')]
00527         #Sort this to be consistent accross CPython, Jython, etc
00528         for i in sorted(self.all_ids()):
00529             n=self.node(i)
00530             if not n.data:
00531                 table.append((str(i),'-',str(n.prev),str(n.succ),'-','-','-','-'))
00532             else:
00533                 tx=n.data.taxon
00534                 if not tx:
00535                     tx='-'
00536                 blength="%0.2f" % n.data.branchlength
00537                 if blength is None:
00538                     blength='-'
00539                     sum_blength='-'
00540                 else:
00541                     sum_blength="%0.2f" % self.sum_branchlength(node=i)
00542                 support=n.data.support
00543                 if support is None:
00544                     support='-'
00545                 else:
00546                     support="%0.2f" % support
00547                 comment=n.data.comment
00548                 if comment is None:
00549                     comment='-'
00550                 table.append((str(i),tx,str(n.prev),str(n.succ),
00551                              blength, sum_blength, support, comment))
00552         print '\n'.join(['%3s %32s %15s %15s %8s %10s %8s %20s' % l for l in table])
00553         print '\nRoot: ',self.root

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.distance (   self,
  node1,
  node2 
)
Add and return the sum of the branchlengths between two nodes.
dist = distance(self,node1,node2)

Definition at line 413 of file Trees.py.

00413 
00414     def distance(self,node1,node2):
00415         """Add and return the sum of the branchlengths between two nodes.
00416         dist = distance(self,node1,node2)
00417         """
00418         
00419         ca=self.common_ancestor(node1,node2)
00420         return self.sum_branchlength(ca,node1)+self.sum_branchlength(ca,node2)

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.get_taxa (   self,
  node_id = None 
)
Return a list of all otus downwards from a node (self, node_id).

nodes = get_taxa(self,node_id=None)

Definition at line 254 of file Trees.py.

00254 
00255     def get_taxa(self,node_id=None):
00256         """Return a list of all otus downwards from a node (self, node_id).
00257 
00258         nodes = get_taxa(self,node_id=None)
00259         """
00260 
00261         if node_id is None:
00262             node_id=self.root
00263         if node_id not in self.chain:
00264             raise TreeError('Unknown node_id: %d.' % node_id)    
00265         if self.chain[node_id].succ==[]:
00266             if self.chain[node_id].data:
00267                 return [self.chain[node_id].data.taxon]
00268             else:
00269                 return None
00270         else:
00271             list=[]
00272             for succ in self.chain[node_id].succ:
00273                 list.extend(self.get_taxa(succ))
00274             return list

Here is the call graph for this function:

Here is the caller graph for this function:

Return a list of all terminal nodes.

Definition at line 275 of file Trees.py.

00275 
00276     def get_terminals(self):
00277         """Return a list of all terminal nodes."""
00278         return [i for i in self.all_ids() if self.node(i).succ==[]]
    

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.has_support (   self,
  node = None 
)
Returns True if any of the nodes has data.support != None.

Definition at line 479 of file Trees.py.

00479 
00480     def has_support(self,node=None):
00481         """Returns True if any of the nodes has data.support != None."""
00482         for n in self._walk(node):
00483             if self.node(n).data.support:
00484                 return True
00485         else:
00486             return False

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.is_bifurcating (   self,
  node = None 
)
Return True if tree downstream of node is strictly bifurcating.

Definition at line 443 of file Trees.py.

00443 
00444     def is_bifurcating(self,node=None):
00445         """Return True if tree downstream of node is strictly bifurcating."""
00446         if node is None:
00447             node=self.root
00448         if node==self.root and len(self.node(node).succ)==3: #root can be trifurcating, because it has no ancestor
00449             return self.is_bifurcating(self.node(node).succ[0]) and \
00450                     self.is_bifurcating(self.node(node).succ[1]) and \
00451                     self.is_bifurcating(self.node(node).succ[2])
00452         if len(self.node(node).succ)==2:
00453             return self.is_bifurcating(self.node(node).succ[0]) and self.is_bifurcating(self.node(node).succ[1])
00454         elif len(self.node(node).succ)==0:
00455             return True
00456         else:
00457             return False

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.is_compatible (   self,
  tree2,
  threshold,
  strict = True 
)
Compares branches with support>threshold for compatibility.

result = is_compatible(self,tree2,threshold)

Definition at line 371 of file Trees.py.

00371 
00372     def is_compatible(self,tree2,threshold,strict=True):
00373         """Compares branches with support>threshold for compatibility.
00374         
00375         result = is_compatible(self,tree2,threshold)
00376         """
00377 
00378         # check if both trees have the same set of taxa. strict=True enforces this.
00379         missing2=set(self.get_taxa())-set(tree2.get_taxa())
00380         missing1=set(tree2.get_taxa())-set(self.get_taxa())
00381         if strict and (missing1 or missing2):
00382             if missing1: 
00383                 print 'Taxon/taxa %s is/are missing in tree %s' % (','.join(missing1) , self.name)
00384             if missing2:
00385                 print 'Taxon/taxa %s is/are missing in tree %s' % (','.join(missing2) , tree2.name)
00386             raise TreeError('Can\'t compare trees with different taxon compositions.')
00387         t1=[(set(self.get_taxa(n)),self.node(n).data.support) for n in self.all_ids() if \
00388             self.node(n).succ and\
00389             (self.node(n).data and self.node(n).data.support and self.node(n).data.support>=threshold)]
00390         t2=[(set(tree2.get_taxa(n)),tree2.node(n).data.support) for n in tree2.all_ids() if \
00391             tree2.node(n).succ and\
00392             (tree2.node(n).data and tree2.node(n).data.support and tree2.node(n).data.support>=threshold)]
00393         conflict=[]
00394         for (st1,sup1) in t1:
00395             for (st2,sup2) in t2:
00396                 if not st1.issubset(st2) and not st2.issubset(st1):                     # don't hiccup on upstream nodes
00397                     intersect,notin1,notin2=st1 & st2, st2-st1, st1-st2                 # all three are non-empty sets
00398                     # if notin1==missing1 or notin2==missing2  <==> st1.issubset(st2) or st2.issubset(st1) ???
00399                     if intersect and not (notin1.issubset(missing1) or notin2.issubset(missing2)):         # omit conflicts due to missing taxa
00400                         conflict.append((st1,sup1,st2,sup2,intersect,notin1,notin2))
00401         return conflict
        

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.is_identical (   self,
  tree2 
)
Compare tree and tree2 for identity.

result = is_identical(self,tree2)

Definition at line 364 of file Trees.py.

00364 
00365     def is_identical(self,tree2):
00366         """Compare tree and tree2 for identity.
00367 
00368         result = is_identical(self,tree2)
00369         """
00370         return self.set_subtree(self.root)==tree2.set_subtree(tree2.root)

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.is_internal (   self,
  node 
)
Returns True if node is an internal node.

Definition at line 283 of file Trees.py.

00283 
00284     def is_internal(self,node):
00285         """Returns True if node is an internal node."""
00286         return len(self.node(node).succ)>0

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.is_monophyletic (   self,
  taxon_list 
)
Return node_id of common ancestor if taxon_list is monophyletic, -1 otherwise.

result = is_monophyletic(self,taxon_list)

Definition at line 421 of file Trees.py.

00421 
00422     def is_monophyletic(self,taxon_list):
00423         """Return node_id of common ancestor if taxon_list is monophyletic, -1 otherwise.
00424         
00425         result = is_monophyletic(self,taxon_list)
00426         """
00427         if isinstance(taxon_list,str):
00428             taxon_set=set([taxon_list])
00429         else:
00430             taxon_set=set(taxon_list)
00431         node_id=self.root
00432         while 1:
00433             subclade_taxa=set(self.get_taxa(node_id))
00434             if subclade_taxa==taxon_set:                                        # are we there?
00435                 return node_id
00436             else:                                                               # check subnodes
00437                 for subnode in self.chain[node_id].succ:
00438                     if set(self.get_taxa(subnode)).issuperset(taxon_set):  # taxon_set is downstream
00439                         node_id=subnode
00440                         break   # out of for loop
00441                 else:
00442                     return -1   # taxon set was not with successors, for loop exhausted

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.is_parent_of (   self,
  parent,
  grandchild 
) [inherited]
Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild).

Definition at line 96 of file Nodes.py.

00096 
00097     def is_parent_of(self,parent,grandchild):
00098         """Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild)."""
00099         if grandchild==parent or grandchild in self.chain[parent].get_succ():
00100             return True
00101         else:
00102             for sn in self.chain[parent].get_succ():
00103                 if self.is_parent_of(sn,grandchild):
00104                     return True
00105             else:
00106                 return False

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.is_preterminal (   self,
  node 
)
Returns True if all successors of a node are terminal ones.

Definition at line 287 of file Trees.py.

00287 
00288     def is_preterminal(self,node):
00289         """Returns True if all successors of a node are terminal ones."""
00290         if self.is_terminal(node):
00291             return False not in [self.is_terminal(n) for n in self.node(node).succ]
00292         else:
            return False

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.is_terminal (   self,
  node 
)
Returns True if node is a terminal node.

Definition at line 279 of file Trees.py.

00279 
00280     def is_terminal(self,node):
00281         """Returns True if node is a terminal node."""
00282         return self.node(node).succ==[]

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.kill (   self,
  id 
) [inherited]
Kills a node from chain without caring to what it is connected: kill(self,id).

Definition at line 67 of file Nodes.py.

00067 
00068     def kill(self,id):
00069         """Kills a node from chain without caring to what it is connected: kill(self,id)."""
00070         if id not in self.chain:
00071             raise ChainException('Unknown ID: '+str(id))
00072         else:
00073             del self.chain[id]

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.link (   self,
  parent,
  child 
) [inherited]
Connects son to parent: link(self,son,parent).

Definition at line 85 of file Nodes.py.

00085 
00086     def link(self, parent,child):
00087         """Connects son to parent: link(self,son,parent)."""
00088         if child not in self.chain:
00089             raise ChainException('Unknown ID: '+str(child))
00090         elif parent not in self.chain:
00091             raise ChainException('Unknown ID: '+str(parent))
00092         else:
00093             self.unlink(child)
00094             self.chain[parent].succ.append(child)
00095             self.chain[child].set_prev(parent)

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.merge_with_support (   self,
  bstrees = None,
  constree = None,
  threshold = 0.5,
  outgroup = None 
)
Merges clade support (from consensus or list of bootstrap-trees) with phylogeny.

tree=merge_bootstrap(phylo,bs_tree=<list_of_trees>)
or
tree=merge_bootstrap(phylo,consree=consensus_tree with clade support)

Definition at line 747 of file Trees.py.

00747 
00748     def merge_with_support(self,bstrees=None,constree=None,threshold=0.5,outgroup=None):
00749         """Merges clade support (from consensus or list of bootstrap-trees) with phylogeny.
00750 
00751         tree=merge_bootstrap(phylo,bs_tree=<list_of_trees>)
00752         or
00753         tree=merge_bootstrap(phylo,consree=consensus_tree with clade support)
00754         """
00755 
00756         if bstrees and constree:
00757             raise TreeError('Specify either list of boostrap trees or consensus tree, not both')
00758         if not (bstrees or constree):
00759             raise TreeError('Specify either list of boostrap trees or consensus tree.')
00760         # no outgroup specified: use the smallest clade of the root
00761         if outgroup is None:
00762             try:
00763                 succnodes=self.node(self.root).succ
00764                 smallest=min([(len(self.get_taxa(n)),n) for n in succnodes]) 
00765                 outgroup=self.get_taxa(smallest[1])
00766             except:
00767                 raise TreeError("Error determining outgroup.")
00768         else: # root with user specified outgroup
00769             self.root_with_outgroup(outgroup)
00770 
00771         if bstrees: # calculate consensus 
00772             constree=consensus(bstrees,threshold=threshold,outgroup=outgroup)
00773         else:
00774             if not constree.has_support():
00775                 constree.branchlength2support()
00776             constree.root_with_outgroup(outgroup)
00777         # now we travel all nodes, and add support from consensus, if the clade is present in both
00778         for pnode in self._walk():
00779             cnode=constree.is_monophyletic(self.get_taxa(pnode))
00780             if cnode>-1:
00781                 self.node(pnode).data.support=constree.node(cnode).data.support
00782 
         

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.node (   self,
  node_id 
)
Return the instance of node_id.

node = node(self,node_id)

Definition at line 186 of file Trees.py.

00186 
00187     def node(self,node_id):
00188         """Return the instance of node_id.
00189         
00190         node = node(self,node_id)
00191         """
00192         if node_id not in self.chain:
00193             raise TreeError('Unknown node_id: %d' % node_id)
00194         return self.chain[node_id]

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.prune (   self,
  taxon 
)
Prunes a terminal taxon from the tree.

id_of_previous_node = prune(self,taxon)
If taxon is from a bifurcation, the connectiong node will be collapsed
and its branchlength added to remaining terminal node. This might be no
longer a meaningful value'

Definition at line 225 of file Trees.py.

00225 
00226     def prune(self,taxon):
00227         """Prunes a terminal taxon from the tree.
00228         
00229         id_of_previous_node = prune(self,taxon)
00230         If taxon is from a bifurcation, the connectiong node will be collapsed
00231         and its branchlength added to remaining terminal node. This might be no
00232         longer a meaningful value'
00233         """
00234         
00235         id=self.search_taxon(taxon)
00236         if id is None:
00237             raise TreeError('Taxon not found: %s' % taxon)
00238         elif id not in self.get_terminals():
00239             raise TreeError('Not a terminal taxon: %s' % taxon)
00240         else:
00241             prev=self.unlink(id)
00242             self.kill(id)
00243             if len(self.node(prev).succ)==1:
00244                 if prev==self.root: # we deleted one branch of a bifurcating root, then we have to move the root upwards
00245                     self.root=self.node(self.root).succ[0]    
00246                     self.node(self.root).branchlength=0.0
00247                     self.kill(prev)
00248                 else: 
00249                     succ=self.node(prev).succ[0]
00250                     new_bl=self.node(prev).data.branchlength+self.node(succ).data.branchlength
00251                     self.collapse(prev)
00252                     self.node(succ).data.branchlength=new_bl
00253             return prev
        

Here is the call graph for this function:

def Bio.Nexus.Trees.Tree.randomize (   self,
  ntax = None,
  taxon_list = None,
  branchlength = 1.0,
  branchlength_sd = None,
  bifurcate = True 
)
Generates a random tree with ntax taxa and/or taxa from taxlabels.
    
new_tree = randomize(self,ntax=None,taxon_list=None,branchlength=1.0,branchlength_sd=None,bifurcate=True)
Trees are bifurcating by default. (Polytomies not yet supported).

Definition at line 487 of file Trees.py.

00487 
00488     def randomize(self,ntax=None,taxon_list=None,branchlength=1.0,branchlength_sd=None,bifurcate=True):
00489         """Generates a random tree with ntax taxa and/or taxa from taxlabels.
00490     
00491         new_tree = randomize(self,ntax=None,taxon_list=None,branchlength=1.0,branchlength_sd=None,bifurcate=True)
00492         Trees are bifurcating by default. (Polytomies not yet supported).
00493         """
00494 
00495         if not ntax and taxon_list:
00496             ntax=len(taxon_list)
00497         elif not taxon_list and ntax:
00498             taxon_list=['taxon'+str(i+1) for i in range(ntax)]
00499         elif not ntax and not taxon_list:
00500             raise TreeError('Either numer of taxa or list of taxa must be specified.')
00501         elif ntax != len(taxon_list):
00502             raise TreeError('Length of taxon list must correspond to ntax.')
00503         # initiate self with empty root
00504         self.__init__()
00505         terminals=self.get_terminals()
00506         # bifurcate randomly at terminal nodes until ntax is reached
00507         while len(terminals)<ntax:
00508             newsplit=random.choice(terminals)
00509             new_terminals=self.split(parent_id=newsplit,branchlength=branchlength)
00510             # if desired, give some variation to the branch length
00511             if branchlength_sd:
00512                 for nt in new_terminals:
00513                     bl=random.gauss(branchlength,branchlength_sd)
00514                     if bl<0:
00515                         bl=0
00516                     self.node(nt).data.branchlength=bl
00517             terminals.extend(new_terminals)
00518             terminals.remove(newsplit)
00519         # distribute taxon labels randomly
00520         random.shuffle(taxon_list)
00521         for (node,name) in zip(terminals,taxon_list):
00522             self.node(node).data.taxon=name

def Bio.Nexus.Trees.Tree.root_with_outgroup (   self,
  outgroup = None 
)

Definition at line 679 of file Trees.py.

00679 
00680     def root_with_outgroup(self,outgroup=None):
00681         
00682         def _connect_subtree(parent,child):
00683             """Hook subtree starting with node child to parent."""
00684             for i,branch in enumerate(self.unrooted):
00685                 if parent in branch[:2] and child in branch[:2]:
00686                     branch=self.unrooted.pop(i)
00687                     break 
00688             else:
00689                 raise TreeError('Unable to connect nodes for rooting: nodes %d and %d are not connected' \
00690                                 % (parent,child))
00691             self.link(parent,child)
00692             self.node(child).data.branchlength=branch[2]
00693             self.node(child).data.support=branch[3]
00694             #now check if there are more branches connected to the child, and if so, connect them
00695             child_branches=[b for b in self.unrooted if child in b[:2]]
00696             for b in child_branches:
00697                 if child==b[0]:
00698                     succ=b[1]
00699                 else:
00700                     succ=b[0]
00701                 _connect_subtree(child,succ) 
00702             
00703         # check the outgroup we're supposed to root with
00704         if outgroup is None:
00705             return self.root
00706         outgroup_node=self.is_monophyletic(outgroup)
00707         if outgroup_node==-1:
00708             return -1
00709         # if tree is already rooted with outgroup on a bifurcating root,
00710         # or the outgroup includes all taxa on the tree, then we're fine
00711         if (len(self.node(self.root).succ)==2 and outgroup_node in self.node(self.root).succ) or outgroup_node==self.root:
00712             return self.root
00713         
00714         self.unroot()
00715         # now we find the branch that connects outgroup and ingroup
00716         #print self.node(outgroup_node).prev
00717         for i,b in enumerate(self.unrooted):
00718             if outgroup_node in b[:2] and self.node(outgroup_node).prev in b[:2]:
00719                 root_branch=self.unrooted.pop(i)
00720                 break
00721         else:
00722             raise TreeError('Unrooted and rooted Tree do not match')
00723         if outgroup_node==root_branch[1]:
00724             ingroup_node=root_branch[0]
00725         else:
00726             ingroup_node=root_branch[1]
00727         # now we destroy the old tree structure, but keep node data. Nodes will be reconnected according to new outgroup
00728         for n in self.all_ids():
00729             self.node(n).prev=None
00730             self.node(n).succ=[]
00731         # now we just add both subtrees (outgroup and ingroup) branch for branch
00732         root=Nodes.Node(data=NodeData())            # new root    
00733         self.add(root)                              # add to tree description
00734         self.root=root.id                           # set as root
00735         self.unrooted.append([root.id,ingroup_node,root_branch[2],root_branch[3]])  # add branch to ingroup to unrooted tree
00736         self.unrooted.append([root.id,outgroup_node,0.0,0.0])   # add branch to outgroup to unrooted tree
00737         _connect_subtree(root.id,ingroup_node)      # add ingroup
00738         _connect_subtree(root.id,outgroup_node)     # add outgroup
00739         # if theres still a lonely node in self.chain, then it's the old root, and we delete it
00740         oldroot=[i for i in self.all_ids() if self.node(i).prev is None and i!=self.root]
00741         if len(oldroot)>1:
00742             raise TreeError('Isolated nodes in tree description: %s' \
00743                             % ','.join(oldroot))
00744         elif len(oldroot)==1:
00745             self.kill(oldroot[0])
00746         return self.root
        

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.search_taxon (   self,
  taxon 
)
Returns the first matching taxon in self.data.taxon. Not restricted to terminal nodes.

node_id = search_taxon(self,taxon)

Definition at line 215 of file Trees.py.

00215 
00216     def search_taxon(self,taxon):
00217         """Returns the first matching taxon in self.data.taxon. Not restricted to terminal nodes.
00218         
00219         node_id = search_taxon(self,taxon)
00220         """
00221         for id,node in self.chain.iteritems():
00222             if node.data.taxon==taxon:
00223                 return id
00224         return None
   

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.set_subtree (   self,
  node 
)
Return subtree as a set of nested sets.

sets = set_subtree(self,node)

Definition at line 345 of file Trees.py.

00345 
00346     def set_subtree(self,node):
00347         """Return subtree as a set of nested sets.
00348 
00349         sets = set_subtree(self,node)
00350         """
00351         
00352         if self.node(node).succ==[]:
00353             return self.node(node).data.taxon
00354         else:
00355             try:
00356                 return frozenset([self.set_subtree(n) for n in self.node(node).succ])
00357             except:
00358                 print node
00359                 print self.node(node).succ
00360                 for n in self.node(node).succ:
00361                     print n, self.set_subtree(n)
00362                 print [self.set_subtree(n) for n in self.node(node).succ]
00363                 raise
            

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.split (   self,
  parent_id = None,
  n = 2,
  branchlength = 1.0 
)
Speciation: generates n (default two) descendants of a node.

[new ids] = split(self,parent_id=None,n=2,branchlength=1.0):

Definition at line 195 of file Trees.py.

00195 
00196     def split(self,parent_id=None,n=2,branchlength=1.0):
00197         """Speciation: generates n (default two) descendants of a node.
00198         
00199         [new ids] = split(self,parent_id=None,n=2,branchlength=1.0):
00200         """ 
00201         if parent_id is None:
00202             raise TreeError('Missing node_id.')
00203         ids=[]
00204         parent_data=self.chain[parent_id].data
00205         for i in range(n):
00206             node=Nodes.Node()
00207             if parent_data:
00208                 node.data=self.dataclass()
00209                 # each node has taxon and branchlength attribute
00210                 if parent_data.taxon:
00211                     node.data.taxon=parent_data.taxon+str(i)
00212                 node.data.branchlength=branchlength
00213             ids.append(self.add(node,parent_id))
00214         return ids

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.sum_branchlength (   self,
  root = None,
  node = None 
)
Adds up the branchlengths from root (default self.root) to node.

sum = sum_branchlength(self,root=None,node=None)

Definition at line 329 of file Trees.py.

00329 
00330     def sum_branchlength(self,root=None,node=None):
00331         """Adds up the branchlengths from root (default self.root) to node.
00332         
00333         sum = sum_branchlength(self,root=None,node=None)
00334         """
00335 
00336         if root is None:
00337             root=self.root
00338         if node is None:
00339             raise TreeError('Missing node id.')
00340         blen=0.0
00341         while node is not None and node is not root: 
00342             blen+=self.node(node).data.branchlength
00343             node=self.node(node).prev
00344         return blen

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Trees.Tree.to_string (   self,
  support_as_branchlengths = False,
  branchlengths_only = False,
  plain = True,
  plain_newick = False,
  ladderize = None,
  ignore_comments = True 
)
Return a paup compatible tree line.
       
to_string(self,support_as_branchlengths=False,branchlengths_only=False,plain=True)

Definition at line 554 of file Trees.py.

00554 
00555     def to_string(self,support_as_branchlengths=False,branchlengths_only=False,plain=True,plain_newick=False,ladderize=None,ignore_comments=True):
00556         """Return a paup compatible tree line.
00557        
00558         to_string(self,support_as_branchlengths=False,branchlengths_only=False,plain=True)
00559         """
00560         # if there's a conflict in the arguments, we override plain=True
00561         if support_as_branchlengths or branchlengths_only:
00562             plain=False
00563         self.support_as_branchlengths=support_as_branchlengths
00564         self.branchlengths_only=branchlengths_only
00565         self.ignore_comments=ignore_comments
00566         self.plain=plain
00567 
00568         def make_info_string(data,terminal=False):
00569             """Creates nicely formatted support/branchlengths."""
00570             # CHECK FORMATTING
00571             if self.plain: # plain tree only. That's easy.
00572                 info_string= ''
00573             elif self.support_as_branchlengths: # support as branchlengths (eg. PAUP), ignore actual branchlengths
00574                 if terminal:    # terminal branches have 100% support
00575                     info_string= ':%1.2f' % self.max_support
00576                 elif data.support:
00577                     info_string= ':%1.2f' % (data.support)
00578                 else:
00579                     info_string=':0.00'
00580             elif self.branchlengths_only: # write only branchlengths, ignore support
00581                 info_string= ':%1.5f' % (data.branchlength)
00582             else:   # write suport and branchlengths (e.g. .con tree of mrbayes)
00583                 if terminal:
00584                     info_string= ':%1.5f' % (data.branchlength)
00585                 else:
00586                     if data.branchlength is not None and data.support is not None:  # we have blen and suppport
00587                         info_string= '%1.2f:%1.5f' % (data.support,data.branchlength)
00588                     elif data.branchlength is not None:                             # we have only blen
00589                         info_string= '0.00000:%1.5f' % (data.branchlength)
00590                     elif data.support is not None:                                  # we have only support
00591                         info_string= '%1.2f:0.00000' % (data.support)
00592                     else:
00593                         info_string= '0.00:0.00000'
00594             if not ignore_comments and hasattr(data,'nodecomment'):
00595                 info_string=str(data.nodecomment)+info_string
00596             return info_string
00597             
00598         def ladderize_nodes(nodes,ladderize=None):
00599             """Sorts node numbers according to the number of terminal nodes."""
00600             if ladderize in ['left','LEFT','right','RIGHT']:
00601                 succnode_terminals=[(self.count_terminals(node=n),n) for n in nodes]
00602                 succnode_terminals.sort()
00603                 if (ladderize=='right' or ladderize=='RIGHT'):
00604                     succnode_terminals.reverse()
00605                 if succnode_terminals:
00606                     succnodes=zip(*succnode_terminals)[1]
00607                 else:
00608                     succnodes=[]
00609             else:
00610                 succnodes=nodes
00611             return succnodes
00612 
00613         def newickize(node,ladderize=None):
00614             """Convert a node tree to a newick tree recursively."""
00615 
00616             if not self.node(node).succ:    #terminal
00617                 return self.node(node).data.taxon+make_info_string(self.node(node).data,terminal=True)
00618             else:
00619                 succnodes=ladderize_nodes(self.node(node).succ,ladderize=ladderize)
00620                 subtrees=[newickize(sn,ladderize=ladderize) for sn in succnodes]
00621                 return '(%s)%s' % (','.join(subtrees),make_info_string(self.node(node).data))
00622                     
00623         treeline=['tree']
00624         if self.name:
00625             treeline.append(self.name)
00626         else:
00627             treeline.append('a_tree')
00628         treeline.append('=')
00629         if self.weight != 1:
00630             treeline.append('[&W%s]' % str(round(float(self.weight),3)))
00631         if self.rooted:
00632             treeline.append('[&R]')
00633         succnodes=ladderize_nodes(self.node(self.root).succ)
00634         subtrees=[newickize(sn,ladderize=ladderize) for sn in succnodes]
00635         treeline.append('(%s)' % ','.join(subtrees))
00636         if plain_newick:
00637             return treeline[-1]
00638         else:
00639             return ' '.join(treeline)+';'
        

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.trace (   self,
  start,
  finish 
) [inherited]
Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end).

Definition at line 107 of file Nodes.py.

00107 
00108     def trace(self,start,finish):
00109         """Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end)."""
00110         if start not in self.chain or finish not in self.chain:
00111             raise NodeException('Unknown node.')
00112         if not self.is_parent_of(start,finish) or start==finish:
00113             return []
00114         for sn in self.chain[start].get_succ():
00115             if self.is_parent_of(sn,finish):
00116                 return [sn]+self.trace(sn,finish)
                

Here is the call graph for this function:

Here is the caller graph for this function:

def Bio.Nexus.Nodes.Chain.unlink (   self,
  id 
) [inherited]
Disconnects node from his predecessor: unlink(self,id).

Definition at line 74 of file Nodes.py.

00074 
00075     def unlink(self,id):
00076         """Disconnects node from his predecessor: unlink(self,id)."""
00077         if id not in self.chain:
00078             raise ChainException('Unknown ID: '+str(id))
00079         else:
00080             prev_id=self.chain[id].prev
00081             if prev_id is not None:
00082                 self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
00083             self.chain[id].prev=None
00084             return prev_id

Here is the caller graph for this function:

Defines a unrooted Tree structure, using data of a rooted Tree.

Definition at line 644 of file Trees.py.

00644 
00645     def unroot(self):
00646         """Defines a unrooted Tree structure, using data of a rooted Tree."""
00647 
00648         # travel down the rooted tree structure and save all branches and the nodes they connect
00649 
00650         def _get_branches(node):
00651             branches=[]
00652             for b in self.node(node).succ:
00653                 branches.append([node,b,self.node(b).data.branchlength,self.node(b).data.support])
00654                 branches.extend(_get_branches(b))
00655             return branches
00656     
00657         self.unrooted=_get_branches(self.root)
00658         # if root is bifurcating, then it is eliminated
00659         if len(self.node(self.root).succ)==2:
00660             # find the two branches that connect to root
00661             rootbranches=[b for b in self.unrooted if self.root in b[:2]]
00662             b1=self.unrooted.pop(self.unrooted.index(rootbranches[0]))
00663             b2=self.unrooted.pop(self.unrooted.index(rootbranches[1]))
00664             # Connect them two each other. If both have support, it should be identical (or one set to None?).
00665             # If both have branchlengths, they will be added
00666             newbranch=[b1[1],b2[1],b1[2]+b2[2]]
00667             if b1[3] is None:
00668                 newbranch.append(b2[3]) # either None (both rootbranches are unsupported) or some support
00669             elif b2[3] is None:
00670                 newbranch.append(b1[3]) # dito
00671             elif b1[3]==b2[3]:          
00672                 newbranch.append(b1[3]) # identical support
00673             elif b1[3]==0 or b2[3]==0:
00674                 newbranch.append(b1[3]+b2[3]) # one is 0, take the other
00675             else:
00676                 raise TreeError('Support mismatch in bifurcating root: %f, %f' \
00677                                 % (float(b1[3]),float(b2[3])))
00678             self.unrooted.append(newbranch)

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Definition at line 50 of file Trees.py.

Definition at line 563 of file Trees.py.

Definition at line 28 of file Nodes.py.

Definition at line 49 of file Trees.py.

Definition at line 29 of file Nodes.py.

Definition at line 564 of file Trees.py.

Definition at line 51 of file Trees.py.

Definition at line 54 of file Trees.py.

Definition at line 565 of file Trees.py.

Definition at line 56 of file Trees.py.

Definition at line 53 of file Trees.py.

Definition at line 562 of file Trees.py.

Definition at line 656 of file Trees.py.

Definition at line 52 of file Trees.py.


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