Method for determining biological expression levels by linear programming

• US 20040014044A1
• Filed: 07/19/2002
• Published: 01/22/2004
• Est. Priority Date: 07/19/2002
• Status: Active Grant

• Current Assignee: University of Chicago
• Original Assignee: University of Chicago
• Inventors: Wright, Stephen J., Clark, Terry, Kurtz, Stuart A., Dyanov, Chris (Hristem), Scott, Ridgway, Quigg, Richard
• Granted Patent: US 7,031,845 B2
• Time in Patent Office: Days
• US Class Current: 435/6
• CPC Class Codes: G16B 25/00 ICT specially adapted for hybridisation; ICT specially adapted for gene or protein expression
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation

Abstract

A method for determining a matrix of expression levels corresponding to a set of biological targets (e.g., genes or gene fragments) and a set of biological samples, including obtaining a matrix of signal values corresponding to the set of biological targets; computing a vector of expression levels for a sample in the set of biological samples using the matrix of signal values; storing the vector of computed expression levels in a storage matrix; repeating the computing and storing steps for each sample in the set of biological samples; and outputting the storage matrix as the matrix of expression levels. The method, based on a linear programming formulation of the problem, works for both “promiscuous” probe array data, in which there may be multiple targets indicated by a single probe, and the “polygamous” case, in which there are multiple probes for a single target. The preferred method can also process data obtained from multiple SAGE analyses using multiple markers. A second embodiment of the method determines optimal expression levels when the available probe data is noisy or uncertain.

Claims

1. A method for determining a matrix of expression levels corresponding to a set of biological targets and a set of biological samples, comprising:

obtaining a matrix of signal values P corresponding to the set of biological targets;

computing a vector of expression levels for a sample in the set of biological samples using the matrix of signal values P;

storing the vector of expression levels computed in the computing step in a storage matrix;

repeating the computing and storing steps for each sample in the set of biological samples; and

outputting the storage matrix as the matrix of expression levels.

2. The method of claim 1, wherein the computing step comprises:

obtaining a vector of signal values A corresponding to the sample;

determining a nonnegative vector E, a nonnegative vector s, and a nonnegative vector t that minimize a total sum of all elements of s and t, and satisfy a constraint PE+s−

t=A; and

setting the vector of expression levels to be the nonnegative vector E determined in the determining step.

3. The method of claim 2, wherein obtaining the vector of signal values A comprises:

testing the sample with an array of reactive probes.

4. The method of claim 2, wherein obtaining the vector of signal values A comprises:

testing the sample with an array of reactive probes, at least one probe in the array of reactive probes being indicative of more than one target in the set of biological targets.

5. The method of claim 2, wherein obtaining the vector of signal values A comprises:

testing the sample with an array of reactive probes, each probe in the array of reactive probes being a sequence of oligonucleotides.

6. The method of claim 2, wherein obtaining the vector of signal values A comprises:

testing the sample with an array of reactive probes including at least one probe which is a sequence of oligonucleotides from at least one part of a known gene.

7. The method of claim 2, wherein the determining step comprises:

identifying a set of biological targets S(A) consistent with the vector of nonnegative signal values A; and

setting, for each target in the set of biological targets that is not in S(A), a respective element of the nonnegative vector E to zero.

8. The method of claim 2, wherein the determining step comprises:

using a linear programming algorithm to determine the nonnegative vector E, the nonnegative vector s, and the nonnegative vector t.

9. The method of claim 8, wherein the determining step further comprises:

constructing a feasible starting point for the linear programming algorithm, for an initial nonnegative vector E_o, by initializing an l-th element of the vector s to be s_l=−

min((PE_o−

A)_l,

     0), and initializing an l-th element of the vector t to be t_l=−

max((PE_o−

A),_l,0).

10. The method of claim 9, wherein the determining step further comprises:

constructing the initial nonnegative vector E_o, by setting each element of E_o to be either zero or, if a corresponding biological target could have uniquely contributed to the vector of signal values A, to a predetermined positive value.

11. The method of claim 2, wherein obtaining the vector of signal values A comprises:

generating a plurality of short nucleotide sequence tags from the sample;

concatenating the plurality of short nucleotide sequence tags into a single molecule;

sequencing the molecule to determine a count for each tag in the plurality of short nucleotide sequence tags; and

mapping the counts determined in the sequencing step into the vector of signal values A.

12. The method of claim 1, wherein the matrix of signal values P obtained in the obtaining step includes more columns than rows.

13. The method of claim 1, wherein obtaining the matrix of signal values P comprises:

testing each target in the set of biological targets with an array of reactive probes.

14. The method of claim 1, wherein obtaining the matrix of signal values P comprises:

testing each target in the set of biological targets with the array of reactive probes,

each target being a gene or a gene fragment.

15. The method of claim 1, wherein the computing step comprises:

obtaining a vector of lower signal values L and a vector of higher signal values H corresponding to the sample, each element of L being less than or equal to a respective element of H;

determining a nonnegative vector E, a nonnegative vector s, and a nonnegative vector t, that minimize a total sum of all elements of s and t, and satisfy constraints s≧

L−

PE and t>

PE−

H; and

setting the vector of expression levels to be the nonnegative vector E determined in the determining step.

16. The method of claim 1, wherein obtaining the matrix of signal values P comprises:

generating a plurality of short nucleotide sequence tags for a target in the set of biological targets;

concatenating the plurality of short nucleotide sequence tags into a single molecule;

sequencing the molecule to determine a count for each tag in the plurality of short nucleotide sequence tags;

mapping the counts determined in the sequencing step into the matrix of signal values P; and

repeating the generating, concatenating, sequencing, and mapping steps for each target in the set of biological targets.

26. A system configured to determine a matrix of expression levels corresponding to a set of biological targets and a set of biological samples by performing the steps recited in any one of claims 1-16.

17. A method for determining a vector of expression levels, comprising:

obtaining a vector of signal values A corresponding to a biological sample;

obtaining a matrix of signal values P corresponding to a set of biological targets;

determining all N nonnegative vectors satisfying an equation PE=A;

outputting, if N=1, the nonnegative vector determined in the determining step as the vector of expression levels;

computing, if N=0, a nonnegative vector E* that minimizes an L₁ norm of an inconsistency in the equation PE=A, and outputting the nonnegative vector E* as the vector of expression levels; and

selecting and outputting, if N>

1, one of the N nonnegative vectors determined in the determining step as the vector of expression levels.

18. The method of claim 17, wherein the selecting and outputting step comprises:

choosing one of the N nonnegative vectors determined in the determining step that minimizes a vector norm, the vector norm being a total sum of all elements.

19. The method of claim 17, wherein the selecting and outputting step comprises:

choosing one of the N nonnegative vectors determined in the determining step that minimizes a vector norm, the vector norm being a total sum of the squares of all elements.

27. A system configured to determine a vector of expression levels by performing the steps recited in any one of claims 17-19.

20. A method for identifying a set of biological targets S(A) consistent with a vector of nonnegative signal values A, comprising:

obtaining a vector of nonnegative signal values P(g) for a target g in a known universe of biological targets U;

determining if, for every positive element of P(g), whether a respective element of A is also positive, and if so, including the target g in the set of biological targets S(A);

repeating the obtaining and determining steps for each target g in the known universe of biological targets U; and

outputting the set of biological targets S(A).

21. A method for identifying a set of uniquely expressed biological targets consistent with a vector of nonnegative signal values A, comprising:

identifying a set of targets S(A) consistent with the vector of nonnegative signal values A;

identifying a set of ambiguous biological targets DS(A) that may be expressed in the vector of nonnegative signal values A, but cannot be identified with certainty; and

outputting those targets that are in S(A), but not in DS(A), as the set of uniquely expressed biological targets consistent with the vector of nonnegative signal values A.

22. The method of claim 21, wherein identifying the set of ambiguous biological targets DS(A) comprises:

computing a multiplicity vector D(A) corresponding to A;

obtaining a vector of nonnegative signal values P(g) for a target g in S(A);

including the target g in DS(A) if, for each positive element of P(g), a respective element of D(A) is at least two; and

repeating the obtaining and including steps for every target g in S(A).

23. The method of claim 22, wherein computing the multiplicity vector D(A) comprises:

initializing D(A) to all zeros;

obtaining a vector of nonnegative signal values P(g_o) for a target go in S(A);

incrementing by one those elements of D(A) that correspond to positive elements of P(g_o); and

repeating the obtaining a vector of nonnegative signal values P(g_o) step and the incrementing step for each target g_o in S(A).

25. The computer program product as claimed in claim 22, wherein the computing step comprises:

obtaining a vector of signal values A corresponding to the sample;

determining a nonnegative vector E, a nonnegative vector s, and a nonnegative vector t that minimize a total sum of all elements of s and t, and satisfy a constraint PE+s−

t=A; and

setting the vector of expression levels to be the nonnegative vector E determined by the preceding determining step.

24. A computer program product configured to store plural computer program instructions which, when executed by a computer, causes the computer to determine a matrix of expression levels corresponding to a set of biological targets and a set of biological samples, by performing plural steps comprising:

obtaining a matrix of signal values P corresponding to the set of biological targets;

computing a vector of expression levels for a sample in the set of biological samples using the matrix of signal values P;

storing the vector of expression levels computed in the computing step in a storage matrix;

repeating the computing and storing steps for each sample in the set of biological samples; and

outputting the storage matrix as the matrix of expression levels.