Method for determining biological expression levels by linear programming
First Claim
1. A computer-implemented method for determining, for a biological sample, a vector of expression levels, each expression level representing a quantity of a target, of a corresponding set of biological targets, that is present in the biological sample, the method comprising:
- obtaining a matrix of signal values P corresponding to the set of biological targets;
obtaining a vector of signal values A corresponding to the biological sample;
determining a vector E, a vector s, and a vector t that minimize a sum of all elements of s and t, and satisfy a constraint PE+s−
t=A, wherein the elements of the vectors E, s, and t are nonnegative real numbers; and
outputting the vector E determined in the determining step as the vector of expression levels.
1 Assignment
0 Petitions
Accused Products
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.
9 Citations
17 Claims
-
1. A computer-implemented method for determining, for a biological sample, a vector of expression levels, each expression level representing a quantity of a target, of a corresponding set of biological targets, that is present in the biological sample, the method comprising:
-
obtaining a matrix of signal values P corresponding to the set of biological targets; obtaining a vector of signal values A corresponding to the biological sample; determining a vector E, a vector s, and a vector t that minimize a sum of all elements of s and t, and satisfy a constraint PE+s−
t=A, wherein the elements of the vectors E, s, and t are nonnegative real numbers; andoutputting the vector E determined in the determining step as the vector of expression levels. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A computer-implemented method for determining, for a biological sample, a vector of expression levels, each expression level representing a quantity of a target, of a corresponding set of biological targets, that is present in the biological sample, the method comprising:
-
obtaining a matrix of signal values P corresponding to the set of biological targets; 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 vector E, a vector s, and a vector t, that minimize a total sum of all elements of s and t, and satisfy constraints s≧
L−
PE and t≧
PE−
H, wherein the elements of the vectors E, s, and t are nonnegative real numbers; andoutputting the vector E determined in the determining step as the vector of expression levels.
-
-
17. A computer program product comprising a computer storage medium configured to store plural computer program instructions which, when executed by a computer, causes the computer to determine, for a biological sample, a vector of expression levels, each expression level representing a quantity of a target, of a corresponding set of biological targets, that is present in the biological sample, by performing plural steps comprising:
-
obtaining a matrix of signal values P corresponding to the set of biological targets; obtaining a vector of signal values A corresponding to the biological sample; determining a vector E, a vector s, and a vector t that minimize a total sum of all elements of s and t, and satisfy a constraint PE+s−
t=A, wherein the elements of the vectors E, s, and t are nonnegative real numbers; andoutputting the vector E determined in the determining step as the vector of expression levels.
-
Specification