← Back to branch summary

~ubuntu-branches/ubuntu/trusty/qiime/trusty

« back to all changes in this revision

Viewing changes to qiime/pycogent_backports/tree.py

  • Committer: Package Import Robot
  • Author(s): Andreas Tille
  • Date: 2013-06-17 18:28:26 UTC
  • mfrom: (9.1.2 sid)
  • Revision ID: package-import@ubuntu.com-20130617182826-376az5ad080a0sfe
Tags: 1.7.0+dfsg-1
Upload preparations done for BioLinux to Debian

Show diffs side-by-side

added added

removed removed

Lines of Context:
qiime/pycogent_backports/tree.py
1
 
#!/usr/bin/env python
2
 
 
3
 
"""additions to cogent.core.tree. 
4
 
 
5
 
Note: these changes are in cogent svn but correctly under the PhyloNode
6
 
object. These cannot be added as member methods to the PhyloNode in here
7
 
because it would require massive awkward changes and adding in a _lot_ of
8
 
modified cogent files into pycogent_backports
9
 
"""
10
 
 
11
 
from numpy import argsort
12
 
 
13
 
__author__ = "Daniel McDonald"
14
 
__copyright__ = "Copyright 2011, The QIIME Project"
15
 
__credits__ = ["Daniel McDonald"]
16
 
__license__ = "GPL"
17
 
__version__ = "1.5.0"
18
 
__maintainer__ = "Daniel McDonald"
19
 
__email__ = "mcdonadt@colorado.edu"
20
 
__status__ = "Release"
21
 
 
22
 
def setMaxTipTipDistance(tree):
23
 
    """Propagate tip distance information up the tree
24
 
 
25
 
    This method was originally implemented by Julia Goodrich with the intent
26
 
    of being able to determine max tip to tip distances between nodes on 
27
 
    large trees efficiently. The code has been modified to track the 
28
 
    specific tips the distance is between
29
 
    """
30
 
    for n in tree.postorder():
31
 
        if n.isTip():
32
 
            n.MaxDistTips = [[0.0, n.Name], [0.0, n.Name]]
33
 
        else:
34
 
            if len(n.Children) == 1:
35
 
                tip_a, tip_b = n.Children[0].MaxDistTips
36
 
                tip_a[0] += n.Children[0].Length or 0.0
37
 
                tip_b[0] += n.Children[0].Length or 0.0
38
 
            else:
39
 
                tip_info = [(max(c.MaxDistTips), c) for c in n.Children]
40
 
                dists = [i[0][0] for i in tip_info]
41
 
                best_idx = argsort(dists)[-2:]
42
 
                tip_a, child_a = tip_info[best_idx[0]]
43
 
                tip_b, child_b = tip_info[best_idx[1]]
44
 
                tip_a[0] += child_a.Length or 0.0
45
 
                tip_b[0] += child_b.Length or 0.0
46
 
            n.MaxDistTips = [tip_a, tip_b]
47
 
 
48
 
def getMaxTipTipDistance(tree):
49
 
    """Returns the max tip tip distance between any pair of tips
50
 
        
51
 
    Returns (dist, tip_names, internal_node)
52
 
    """
53
 
    if not hasattr(tree, 'MaxDistTips'):
54
 
        setMaxTipTipDistance(tree)
55
 
 
56
 
    longest = 0.0
57
 
    names = [None,None]
58
 
    best_node = None
59
 
    for n in tree.nontips(include_self=True):
60
 
        tip_a, tip_b = n.MaxDistTips
61
 
        dist = (tip_a[0] + tip_b[0])
62
 
 
63
 
        if dist > longest:
64
 
            longest = dist
65
 
            best_node = n
66
 
            names = [tip_a[1], tip_b[1]]
67
 
    return longest, names, best_node
68