def clusterSimrelMatrix(matrix, terms, ancestors, p,
                        counts, term2pvalue, go2info, options):
    '''apply revigo clustering scheme to *matrix*.

    *ancestors*, *p*, and *counts* contain auxiliary data

    ancestors: dictionary mapping a term to all its ancestors
    p: dictionary mapping a term to its annotation frequency
    counts: dictionary mapping a term to all the genes it is annotated with
    go2info: dictionary mapping a term to its description
    term2pvalue: dictionary mapping a term to its p-value

    returns (matrix, terms)
    '''

    # cluster or load clustered simrel matrix
    E.info("working on simrel matrix with %i terms" % len(terms))
    term2index = dict([(y, x) for x, y in enumerate(terms)])

    # shrink matrix to only those terms that are in result set
    terms = [x for x in terms if x in term2pvalue]

    E.info("after removing terms with no p-value: %i terms" % len(terms))
    if len(terms) == 0:
        E.warn("no terms given after p-value filtering")
        return None, [], []

    matrix = matrix[numpy.array([term2index[x] for x in terms])]
    matrix = matrix[:, numpy.array([term2index[x] for x in terms])]
    term2index = dict([(y, x) for x, y in enumerate(terms)])

    # cluster according to revigo
    clusters = dict([(x, [x]) for x in terms])
    nrows = len(terms)

    counter = E.Counter()

    # row/column indices of members
    member_indices = []

    while 1:
        # find most similar pair of GO terms ti and tj with similarity simrel
        index = numpy.argmax(matrix)
        i = index // nrows
        j = index % nrows

        simrel = matrix[i][j]
        assert simrel == matrix.max()

        # stop procedure if similarity is below threshold
        if simrel == 0:
            E.debug("similarity reached 0 - done")
            break

        if simrel < options.max_simrel_threshold:
            E.debug("similarity %f < %f - done" %
                    (simrel, options.max_simrel_threshold))
            break

        nclusters = len(clusters)
        if nclusters <= options.min_clusters_threshold:
            E.debug("%i clusters reached at similarity %f - done" %
                    (nclusters, simrel))
            break

        t1 = terms[i]
        t2 = terms[j]
        E.debug("clustering at similarity %f (%i,%i)" % (simrel, i, j))

        p1 = term2pvalue[t1]
        p2 = term2pvalue[t2]

        E.debug("1. %s (%s): pvalue=%f, freq=%f" %
                (t1, go2info.get(t1, "na"), p1, p[t1] * 100.0))
        E.debug("2. %s (%s): pvalue=%f, freq=%f" %
                (t2, go2info.get(t2, "na"), p2, p[t2] * 100.0))

        counter.tested += 1

        if p[t1] > options.min_frequency:
            # remove term with frequency > 5%
            counter.min_frequency += 1
            rep, mem = t2, t1

        elif p[t2] > options.min_frequency:
            # remove term with frequency > 5%
            counter.min_frequency += 1
            rep, mem = t1, t2

        elif term2pvalue[t1] < term2pvalue[t2]:
            # remove term with higher pvalue
            counter.min_pvalue += 1
            rep, mem = t1, t2

        elif term2pvalue[t2] < term2pvalue[t1]:
            # remove term with higher pvalue
            counter.min_pvalue += 1
            rep, mem = t2, t1

        elif t1 in ancestors[t2]:
            # t1 is parent of t2 - reject child term t2
            ovl = float(len(counts[t1].intersection(counts[t2])))
            if (ovl / len(counts[t1])) >= options.min_child_threshold:
                # exception: if parent is > 75% child, keep child
                counter.ancestor_child += 1
                rep, mem = t2, t1
            else:
                counter.ancestor_parent += 1
                rep, mem = t1, t2

        elif t2 in ancestors[t1]:
            # t2 is parent of t1 - reject child term t1
            ovl = float(len(counts[t1].intersection(counts[t2])))
            if (ovl / len(counts[t2])) >= options.min_child_threshold:
                # exception: if parent is > 75% child, keep child
                counter.ancestor_child += 1
                rep, mem = t1, t2
            else:
                counter.ancestor_parent += 1
                rep, mem = t2, t1

        else:
            # keep random term
            counter.random += 1
            rep, mem = min(t1, t2), max(t1, t2)

        # merge clusters
        clusters[rep].extend(clusters[mem])
        del clusters[mem]
        # set values of mem to 0
        if mem == t1:
            matrix[i, :] = 0
            matrix[:, i] = 0
            member_indices.append(i)
        else:
            matrix[j, :] = 0
            matrix[:, j] = 0
            member_indices.append(j)

    E.info("%s" % str(counter))
    E.info("after clustering: %i clusters" % len(clusters))

    # shrink matrix
    member_indices = set(member_indices)
    rep_indices = [x for x in xrange(nrows) if x not in member_indices]
    terms = [terms[x] for x in rep_indices]
    # rows = len(terms)
    matrix = matrix[numpy.array([x for x in rep_indices])]
    matrix = matrix[:, numpy.array([x for x in rep_indices])]

    return matrix, terms, clusters
dataset/ETHPy150Open CGATOxford/cgat/scripts/revigo.py/clusterSimrelMatrix/original