Method and system for determining optimal sequences
OwnerRichard J. Carterinventor
Life of this patent
Estimating the term…
Abstract
A method and system for searching for an optimal sequence of subunits from among possible sequences of subunits. A described embodiment provides for evaluating each possible subunit sequence of a biopolymer with respect to a mass spectrum produced by ionizing and fragmenting the mass-tagged biopolymer in order to determine the most probable subunit sequence of the biopolymer. However, unlike in the currently practiced, permutations-based methods, an efficient combinations-based search is used to hierarchically partition all possible subunit sequences, and to assign maximum subunit-sequence rankings to the partitions, in order to computationally efficiently extract the most probable subunit sequence.
Claims21
A method for searching for an optimal sequence of subunits from among possible sequences of subunits of a given length p, the subunits having subunit types selected from a set of subunit types T of size n, a function F applied to a sequence of subunits to produce a ranking for the sequence of subunits, the ranking produced by the function F for the optimal sequence of subunits greater than rankings obtained by applying the function F to all non-optimal sequences of subunits, the method comprising:
- calculating a ranking for each possible subunit combination of length between I and p including combinations with duplicated subunits, a ranking of a combination of subunits being equal to a ranking of a greatest ranked sequence that is one permutation of the combination of subunits;
- and
- determining the optimal subunit sequence from the calculated subunit-combination rankings.
A method for determining the subunit sequence of length p of a mass-tagged biopolymer from a mass spectrum of the mass-tagged biopolymer, the method comprising:
- providing a function MS that returns a score reflective of a probability that a specified ion contributed to the mass spectrum;
- calculating a ranking for each possible subunit combination of length between 1 and p, including combinations with duplicated subunits, a ranking of a combination of subunits equal to a ranking of a greatest ranked sequence that is one permutation of the combination of subunits;
- and
- determining the subunit sequence of a mass-tagged biopolymer by determining a greatest ranked subunit sequence of length p from the greatest ranked combination of length p and a sequence of greatest ranked immediate subcombinations of the greatest ranked combination of length p of monotonically decreasing lengths of from p−1 to 1.
A method for determining a particular sequence of n entities from among a large number of sequence-of-entity permutations, the method comprising:
- providing a function that scores a specified sequence;
- determining the set of combinations with replacement of entities having between 1 and n entities;
- determining for each combination with replacement of entities with 1 entity a combination ranking determined by applying the function to the entity contained in the combination with replacement;
- determining, for each combination with replacement of entities with more than 1 entity a combination ranking determined by applying the function to a sequence of entities representing a permutation of the entities contained in the combination of replacement of entities and adding to a result of the function a greatest ranking obtained for an immediate subcombination of the combination;
- and
- determining the particular sequence from the determined combinations with replacement having greatest rankings.
Dependencies are inferred from the claim text.