Function naive_motifs

tests/test_motifs.py:12–83

(T, m, max_motifs, max_matches, T_subseq_isconstant=None)

def naive_motifs(T, m, max_motifs, max_matches, T_subseq_isconstant=None):
    # To avoid complexity, this naive function is written
    # such that each array in the ouput has shape
    # (max_motif, max_matches).

    # To this end, the following items are considered:
    # 1. `max_distance` and `cutoff` are both hardcoded and
    # set to np.inf
    # 2. If the number of subsequence, i.e. `len(T)-m+1`, is
    # not less than `m * max_motifs * max_matches`, then the
    # output definitely has the shape (max_motif, max_matches).

    l = len(T) - m + 1
    excl_zone = int(np.ceil(m / 4))
    T_subseq_isconstant = naive.rolling_isconstant(T, m, T_subseq_isconstant)

    output_shape = (max_motifs, max_matches)
    motif_distances = np.full(output_shape, -np.inf, dtype=np.float64)
    motif_indices = np.full(output_shape, -1, dtype=np.int64)

    D = naive.distance_matrix(T, T, m)
    D[np.isnan(D)] = np.inf
    for i in range(D.shape[0]):
        for j in range(D.shape[1]):
            if np.isfinite(D[i, j]):
                if T_subseq_isconstant[i] and T_subseq_isconstant[j]:
                    D[i, j] = 0.0
                elif T_subseq_isconstant[i] or T_subseq_isconstant[j]:
                    D[i, j] = np.sqrt(m)
                else:  # pragma: no cover
                    pass

    for i in range(D.shape[0]):
        naive.apply_exclusion_zone(D[i], i, excl_zone, np.inf)

    P = np.min(D, axis=1)
    for i in range(max_motifs):
        distances = []
        indices = []

        idx = np.argmin(P)

        # self match
        distances.append(0)
        indices.append(idx)
        naive.apply_exclusion_zone(P, idx, excl_zone, np.inf)

        # Explore distance profile D[idx] till `max_matches` are found.
        naive.apply_exclusion_zone(D[idx], idx, excl_zone, np.inf)
        for _ in range(l):
            if len(distances) >= max_matches:
                break

            nn = np.argmin(D[idx])
            distances.append(D[idx, nn])
            indices.append(nn)

            # Update D[idx] to avoid finding matches that are trivial to