def _lineage(TreeNode):
    lineage = [node.name for node in TreeNode.ancestors()]
    lineage = lineage[::-1] #lowest to highest node order
    if not TreeNode.is_tip():
        lineage.append(TreeNode.name)
    lineage = ";".join(lineage[1:]) #first node -- the root -- has no name
    return lineage

 def depth_partition(self, input_tree, percentile, output_tree):
     '''
     Attempt to cluster tree with nodes of tip-to-tip distrubution <
     an nth percentile cutoff of the whole-tree distance distribution. 
     A better description can be found in the citation below.
     
     Parameters
     ----------
     tree: skbio TreeNode obj
         http://scikit-bio.org/docs/latest/generated/skbio.tree.TreeNode.html #skbio.tree.TreeNode
             
     percentile: float
         The percentile cutoff to use to determine the cutoff from clading
         from a given node.
     
     Clustering method modified from Prosperi et al method:
     Prosperi, M.C.F., et al. A novel methodology for large-scale phylogeny 
     partition. Nat. Commun. 2:321 doi: 10.1038/ncomms1325 (2011).
     
     http://www.nature.com/ncomms/journal/v2/n5/full/ncomms1325.html
     '''
     tree = TreeNode.read(input_tree)
     tree = tree.root_at_midpoint()
     cluster_count = 1
     clustered = set()
     clusters = {}
     logging.debug("Calculating %ith percentile cutoff from root" \
                                             % (percentile))
     whole_tree_distribution = self._node_dist(tree)
     
     cutoff = np.percentile(whole_tree_distribution, percentile)
     logging.debug("Cutoff (%ith percentile): %f" % (percentile,
                                                     cutoff))
     for node in tree.preorder():
         if node in clustered:
             continue
         elif node.is_tip():
             continue
         else:
             node_distribution = self._node_dist(node)
             median=np.median(node_distribution)
             logging.debug("Median of node: %f" % median)
             if median <= cutoff:
                 logging.debug("Cluster found!")
                 cluster_name =  "partition_%i" % (cluster_count)
                 clusters[cluster_name] = [x.name.replace(' ','_') 
                                           for x in node.tips()]
                 self._rename(node, cluster_name)
                 cluster_count+=1
                 for descenent in node.traverse():
                     clustered.add(descenent)
     logging.info("%i depth cluster(s) found in tree" % (cluster_count-1))
     tree.write(output_tree, "newick")
     
     logging.debug("Recording tips that were not partitioned")
     clusters[self.UNCLUSTERED] = []
     for tip in tree.tips():
         if tip not in clustered:
             clusters[self.UNCLUSTERED].append(tip.name.replace(' ','_'))
     return clusters

    def unifrac(self, weighted=True, rank="auto"):
        """A beta diversity metric that takes into account the relative relatedness of community
        members. Weighted UniFrac looks at abundances, unweighted UniFrac looks at presence.

        Parameters
        ----------
        weighted : `bool`
            Calculate the weighted (True) or unweighted (False) distance metric.
        rank : {'auto', 'kingdom', 'phylum', 'class', 'order', 'family', 'genus', 'species'}, optional
            Analysis will be restricted to abundances of taxa at the specified level.

        Returns
        -------
        skbio.stats.distance.DistanceMatrix, a distance matrix.
        """
        # needs read counts, not relative abundances
        if self._guess_normalized():
            raise OneCodexException("UniFrac requires unnormalized read counts.")

        df = self.to_df(rank=rank, normalize=False)

        counts = []
        for c_id in df.index:
            counts.append(df.loc[c_id].tolist())

        tax_ids = df.keys().tolist()

        tree = self.tree_build()
        tree = self.tree_prune_rank(tree, rank=df.ocx_rank)

        # there's a bug (?) in skbio where it expects the root to only have
        # one child, so we do a little faking here
        from skbio.tree import TreeNode

        new_tree = TreeNode(name="fake root")
        new_tree.rank = "no rank"
        new_tree.append(tree)

        # then finally run the calculation and return
        if weighted:
            return skbio.diversity.beta_diversity(
                "weighted_unifrac", counts, df.index.tolist(), tree=new_tree, otu_ids=tax_ids
            )
        else:
            return skbio.diversity.beta_diversity(
                "unweighted_unifrac", counts, df.index.tolist(), tree=new_tree, otu_ids=tax_ids
            )

 def testFindParents(self):
     ann = TreeAnnotator()
     
     tree = TreeNode.read(StringIO("(((A:1, B:2)'g__genus1':3, (C:4, D:5)'g__genus2':6)'f__family':10)root;"))
     assert_equals('g__genus1', ann.find_named_parent(tree, tree.find('B')).name, 'self is named')
     
     tree = TreeNode.read(StringIO("(((A:1, 2475:2)'g__genus1':3, (C:4, D:5)'g__genus2':6)'f__family':10)root;"))
     assert_equals('g__genus1', ann.find_named_parent(tree, tree.find('2475')).name, 'parent directly above')
     
     tree = TreeNode.read(StringIO("(((A:1, 2475:2):3, (C:4, D:5)'g__genus2':6)'f__family':10)root;"))
     assert_equals('f__family', ann.find_named_parent(tree, tree.find('2475')).name, 'parent 2 above')
     
     tree = TreeNode.read(StringIO("(((A:1, 2475:2):3, (C:4, D:5)'g__genus2':6)'f__family':10);"))
     assert_equals(None, ann.find_named_parent(tree, tree.find('f__family').parent), 'parent of root')
     
     tree = TreeNode.read(StringIO("(((A:1, 2475:2):3, (C:4, D:5)'g__genus2':6):10);"))
     assert_equals(None, ann.find_named_parent(tree, tree.find('g__genus2').parent), 'no parent before root')

def generate_html_summary(qclient, job_id, parameters, out_dir):
    """Generates the HTML summary of a BIOM artifact

    Parameters
    ----------
    qclient : qiita_client.QiitaClient
        The Qiita server client
    job_id : str
        The job id
    parameters : dict
        The parameter values to validate and create the artifact
    out_dir : str
        The path to the job's output directory

    Returns
    -------
    bool, None, str
        Whether the job is successful
        Ignored
        The error message, if not successful
    """
    # Step 1: gather file information from qiita using REST api
    artifact_id = parameters['input_data']
    qclient_url = "/qiita_db/artifacts/%s/" % artifact_id
    artifact_info = qclient.get(qclient_url)

    # Step 2: get the mapping file, depends if analysis or not
    if artifact_info['analysis'] is None:
        is_analysis = False
        qurl = ('/qiita_db/prep_template/%s/' %
                artifact_info['prep_information'][0])
        md = qclient.get(qurl)['qiime-map']
    else:
        is_analysis = True
        qurl = '/qiita_db/analysis/%s/metadata/' % artifact_info['analysis']
        md = qclient.get(qurl)

    tree = None
    if 'plain_text' in artifact_info['files']:
        tree = TreeNode.read(artifact_info['files']['plain_text'][0])

    # Step 3: generate HTML summary
    # if we get to this point of the code we are sure that this is a biom file
    # and that it only has one element
    index_fp, viz_fp, qza_fp = _generate_html_summary(
        artifact_info['files']['biom'][0], md, out_dir, is_analysis, tree)

    # Step 4: add the new file to the artifact using REST api
    success = True
    error_msg = ""
    try:
        qclient.patch(qclient_url, 'add', '/html_summary/',
                      value=dumps({'html': index_fp, 'dir': viz_fp}))
    except Exception as e:
        success = False
        error_msg = str(e)

    return success, None, error_msg

def get_clusters(x_original, axis='row'):
    """Performs UPGMA clustering using euclidean distances"""
    x = x_original.copy()
    if axis == 'column':
        x = x.T
    nr = x.shape[0]
    row_dissims = pw_distances(x, ids=map(str, range(nr)), metric='euclidean')
    # do upgma - rows
    # Average in SciPy's cluster.hierarchy.linkage is UPGMA
    linkage_matrix = linkage(row_dissims.condensed_form(), method='average')
    tree = TreeNode.from_linkage_matrix(linkage_matrix, row_dissims.ids)
    return [int(tip.name) for tip in tree.tips()]

    def tree_build(self):
        """Build a tree from the taxonomy data present in this `ClassificationsDataFrame` or
        `SampleCollection`.

        Returns
        -------
        `skbio.tree.TreeNode`, the root node of a tree that contains all the taxa in the current
        analysis and their parents leading back to the root node.
        """
        from skbio.tree import TreeNode

        # build all the nodes
        nodes = {}

        for tax_id in self.taxonomy.index:
            node = TreeNode(name=tax_id, length=1)
            node.tax_name = self.taxonomy["name"][tax_id]
            node.rank = self.taxonomy["rank"][tax_id]
            node.parent_tax_id = self.taxonomy["parent_tax_id"][tax_id]

            nodes[tax_id] = node

        # generate all the links
        for tax_id in self.taxonomy.index:
            try:
                parent = nodes[nodes[tax_id].parent_tax_id]
            except KeyError:
                if tax_id != "1":
                    warnings.warn(
                        "tax_id={} has parent_tax_id={} which is not in tree"
                        "".format(tax_id, nodes[tax_id].parent_tax_id)
                    )

                continue

            parent.append(nodes[tax_id])

        return nodes["1"]

    def testTipToCluster(self):
        tree = TreeNode.read(StringIO('((F:20, ((A:11, B:12):10, (H:8, D:9):3):20)G:30)root;'))
        clusters = Tree2Tax().named_clusters_for_several_thresholds(tree, [40, 25])
        self.assertSameClusterSets([[25,[['F'], _('A B'), _('D H')]], [40,[['F'], _('A B D H')]]], clusters)
        assert_equals(_('G.3 G.1 G.2'), [c.name() for c in clusters[0].clusters])
        assert_equals(_('G.2 G.1'), [c.name() for c in clusters[1].clusters])
         
        tip = tree.find('F')
        assert_equals('G.3', clusters[0].tip_to_cluster(tip).name())
        assert_equals('G.2', clusters[1].tip_to_cluster(tip).name())
 
        tip = tree.find('D')
        assert_equals('G.2', clusters[0].tip_to_cluster(tip).name())
        assert_equals('G.1', clusters[1].tip_to_cluster(tip).name())

def get_clusters(x_original, axis=['row', 'column'][0]):
    """Performs UPGMA clustering using euclidean distances"""
    x = x_original.copy()
    if axis == 'column':
        x = x.T
    nr = x.shape[0]
    metric_f = get_nonphylogenetic_metric('euclidean')
    row_dissims = DistanceMatrix(metric_f(x), map(str, range(nr)))
    # do upgma - rows
    # Average in SciPy's cluster.heirarchy.linkage is UPGMA
    linkage_matrix = linkage(row_dissims.condensed_form(), method='average')
    tree = TreeNode.from_linkage_matrix(linkage_matrix, row_dissims.ids)
    row_order = [int(tip.name) for tip in tree.tips()]
    return row_order

def load_tree_files(tree_dir):
    """Load trees from filepaths

    checks if  filenames indicate that trees are from different
    distance methods.  If so, warns user.
    loads trees into phylonode objects
    returns [trees]
    raises a RuntimeError if no  trees are loaded
    """
    tree_file_names = os.listdir(tree_dir)
    # ignore invisible files like .DS_Store
    tree_file_names = [fname for fname in tree_file_names if not
                       fname.startswith('.')]

    # try to warn user if using multiple types of trees {
    try:
        base_names = []
        for fname in tree_file_names:
            base_names.append(parse_rarefaction_fname(fname)[0])
    except ValueError:
        pass
    else:
        if len(set(base_names)) > 1:
            warnstr = """
warning: trees are named differently, please be sure you're not
comparing trees generated in different manners, unless you're quite sure
that's what you intend to do.  types: """ + str(set(base_names)) + """
continuing anyway..."""
            warn(warnstr)
    # }
    trees = []
    for fname in tree_file_names:
        try:
            f = open(os.path.join(tree_dir, fname), 'U')
            tree = TreeNode.from_newick(f)
            tree.filepath = fname
            trees.append(tree)
            f.close()
        except IOError as err:
            sys.stderr.write('error loading tree ' + fname + '\n')
            exit(1)
    if len(trees) == 0:
        raise RuntimeError('Error: no trees loaded' +
                           ', check that tree directory has has valid trees')
    return trees

def write_tree(cluster_method):
    import scipy.spatial.distance as ssd
    dmx = pd.read_csv("distance_matrix", index_col=0, sep="\t")
    ids = dmx.index.tolist()
    #triu = np.square(dmx.as_matrix())
    triu = np.square(dmx.values)
    distArray = ssd.squareform(triu)
    if cluster_method == "average":
        hclust = average(distArray)
    elif cluster_method == "weighted":
        hclust = weighted(distArray)
    else:
        print("invalid cluster method chosen")
        sys.exit()
    t = TreeNode.from_linkage_matrix(hclust, ids)
    nw = t.__str__().replace("'", "")
    outfile = open("bsr_matrix.tree", "w")
    outfile.write(nw)
    outfile.close()

def single_file_upgma(input_file, output_file):
    # read in dist matrix
    dist_mat = DistanceMatrix.read(input_file)

    # SciPy uses average as UPGMA:
    # http://docs.scipy.org/doc/scipy/reference/generated/
    #    scipy.cluster.hierarchy.linkage.html#scipy.cluster.hierarchy.linkage
    linkage_matrix = linkage(dist_mat.condensed_form(), method='average')

    tree = TreeNode.from_linkage_matrix(linkage_matrix, dist_mat.ids)

    # write output
    f = open(output_file, 'w')
    try:
        f.write(tree.to_newick(with_distances=True))
    except AttributeError:
        if c is None:
            raise RuntimeError("""input file %s did not make a UPGMA tree.
 Ensure it has more than one sample present""" % (str(input_file),))
        raise
    f.close()

    def _open_tree(self, tree_path):
        '''
        Open a tree file, determine what decorations are already present. Strip
        Unwanted decoration
        
        Parameters
        ----------
        tree_path: str
            Path to a file containing a phylogenetic tree, in Newick format.
            
        Returns
        -------
        skbio TreeNode object
        '''
        tree_obj=TreeNode.read(open(tree_path))
        bootstrapped = True
        for node in tree_obj.non_tips():
            if node.name:
                try:
                    float(node.name)
                except:
                    logging.debug("Tree is decorated already. Stripping all \
    previous decoration from the tree.")
                    bootstrapped = False
                    tree_obj = self._strip_tree(tree_obj)
                    break
            else:
                if bootstrapped:
                    logging.warning("This tree doesn't appear correctly \
formatted or there is information missing. No boostrap value or decoration \
found for bare node. ")
                    bootstrapped = False
        if bootstrapped:
            logging.debug("Tree is bootstrap or has confidence values \
assigned to the nodes.")
        return tree_obj

 def result_constructor(x):
     return TreeNode.read(StringIO(x), format='newick')

 def test_missing_taxonomy(self):
     tree = TreeNode.read(StringIO('((((A:11, B:12)C:10, D:9)E:20, F:20)G:30)root;'))
     assert_equals(['C'], TaxonomyFunctions().missing_taxonomy(tree, tree.find('A'), tree.find('E')))
     assert_equals([], TaxonomyFunctions().missing_taxonomy(tree, tree.find('A'), tree.find('A')))
     assert_equals(['E','C'], TaxonomyFunctions().missing_taxonomy(tree, tree.find('A'), tree.find('G')))

 def testSimple(self):
     tree = TreeNode.read(StringIO('((A:0.11, B:0.12)C:0.1, D:0.2)root;'))
     clusters = Tree2Tax().named_clusters(tree, 0.25)
     self.assertSameClusters([['A','B'],['D']], clusters)

 def testNoClusering(self):
     tree = TreeNode.read(StringIO('((A:0.11, B:0.12)C:0.1, D:0.2)root;'))
     clusters = Tree2Tax().named_clusters(tree, 0.05)
     self.assertSameClusters([['A'],['B'],['D']], clusters)
     assert_equals(_('C.1 C.2 Root'), [c.name() for c in clusters])

 def testClusterEverything(self):
     tree = TreeNode.read(StringIO('((A:0.11, B:0.12)C:0.1, D:0.2)root;'))
     clusters = Tree2Tax().named_clusters(tree, 0.5)
     self.assertSameClusters([['A','B','D']], clusters)
     assert_equals('Root',clusters[0].name())

 def testFullTaxonomy(self):
     ann = TreeAnnotator()
     tree = TreeNode.read(StringIO("(((A:1, B:2):3, (C:4, D:5)'g__genus2':6)'f__family':10)root;"))
     assert_equals('f__family; g__genus2', ann.full_taxonomy(tree, tree.find('D')))

 def testClusterNamingOnTwoInternalNodesReverseOrder(self):
     tree = TreeNode.read(StringIO('((F:20, ((A:11, B:12):10, (H:8, D:9):3):20)G:30)root;'))
     clusters = Tree2Tax().named_clusters(tree, 40)
     self.assertSameClusters([['F'], _('A B D H')], clusters)
     assert_equals(_('G.2 G.1'), [c.name() for c in clusters])