SCALABLE SPECTRAL MODELING OF SPARSE SEQUENCE FUNCTIONS VIA A BEST MATCHING ALGORITHM

摘要

A method for modeling a sparse function over sequences is described. The method includes inputting a set of sequences that support a function. A set of prefixes and a set of suffixes for the set of sequences are identified. A sub-block of a full matrix is identified which has the full structural rank as the full matrix. The full matrix includes an entry for each pair of a prefix and a suffix from the sets of prefixes and suffixes. A matrix for the sub-block is computed. A minimal non-deterministic weighted automaton which models the function is computed, based on the sub-block matrix. Information based on the identified minimal non-deterministic weighted automaton is output.