Genetic algorithms for optimization of genomics-based medical diagnostic tests

• US 20070172828A1
• Filed: 02/01/2005
• Published: 07/26/2007
• Est. Priority Date: 02/10/2004
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Simpson, Mark, Schaffer, J.
• Granted Patent: US 8,798,937 B2
• Time in Patent Office: Days
• US Class Current: 435/6
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• 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
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/10 Signal processing, e.g. from mass spectrometry [MS] or from PCR

Abstract

In a genetic optimization method, the genes of a chromosome population are computationally genetically evolved. The evolving includes evolving a number of expressed genes in each chromosome and employing a fitness criterion evaluated without reference to unexpressed genes of each chromosome. An optimized chromosome produced by the genetic evolving is selected.

Claims

1. A method for determining a classifier, the method comprising:

producing a first generation chromosome population of chromosomes, each chromosome having (i) a selected number of genes specifying a sub-set of an associated set of measurements and (ii) an expressed sub-set-size gene having a value distinguishing expressed and unexpressed genes of the chromosome;

computationally genetically evolving the genes of the chromosomes including the expressed sub-set-size gene respective to a fitness criterion evaluated without reference to unexpressed genes to produce successive generation chromosome populations; and

selecting a classifier that uses the sub-set of associated measurements specified by the expressed genes of a chromosome identified by the genetic evolving.

2. The method as set forth in claim 1, wherein the genes of each chromosome define an ordered set, and the expressed sub-set-size gene contains an ordinal position value separating the expressed and unexpressed genes in the ordered set.

3. The method as set forth in claim 21, wherein the genetic evolving includes:

generating offspring chromosomes by mating selected parent chromosomes of the present chromosome population, each offspring chromosome having an expressed sub-set-size gene value within a range defined by expressed sub-set-size gene values of the parent chromosomes from which that offspring chromosome is generated.

4. The method as set forth in claim 3, wherein the range defined by the expressed sub-set-size gene values of the parent chromosomes includes at least one of:

(i) a value larger than a largest one of the expressed sub-set-size gene values of the parent chromosomes, and

(ii) a value smaller than a smallest one of the expressed sub-set-size gene values of the parent chromosomes.

5. The method as set forth in claim 2, wherein the ordered set of genes has first and second ends with the gene closest to the first end being an expressed gene, and the genetic evolving includes:

generating offspring chromosomes, each offspring chromosome being generated from two parent chromosomes of the present chromosome population by;

(i) filling genes of the offspring chromosome with gene values common to both parent chromosomes using the ordering of the common gene values in a selected one of the two parent chromosomes and biasing the filling toward the first end of the ordered set of genes of the offspring chromosome and (ii) filling remaining genes with gene values that are unique to one or other of the parent chromosomes.

6. The method as set forth in claim 5, wherein the filling of genes with gene values common to both parent chromosomes includes:

at least occasionally varying the ordering of the common gene values in the offspring chromosome from the ordering of the common gene values in the selected one of the two parent chromosomes.

7. The method as set forth in claim 1, wherein the genetic evolving includes:

generating offspring chromosomes having (i) values of genes other than the expressed sub-set-size gene selected from a group consisting of the set of values of genes of the parent chromosomes other than the expressed sub-set-size genes of the parent chromosomes and (ii) a value of the expressed sub-set-size gene selected within a range defined by the expressed sub-set-size gene values of the parent chromosomes.

8. The method as set forth in claim 1, wherein the genetic evolving includes:

generating offspring chromosomes, each offspring chromosome being generated from two parent chromosomes of the present chromosome population by;

(i) filling genes of the offspring chromosome with gene values common to both parent chromosomes and (ii) filling remaining genes with gene values that are unique to one or the other of the parent chromosomes; and

selectively mutating genes values of the offspring chromosomes that are unique to one or the other of the parent chromosomes without mutating gene values of the offspring chromosomes that are common to both parent chromosomes, a mutation rate for the selective mutating of gene values that are unique to one or the other of the parent chromosomes being greater than 5%.

9. The method as set forth in claim 1, wherein the computational genetic evolving includes:

generating offspring chromosomes from selected combinations of chromosomes of the present generation chromosome population; and

replacing a selected chromosome of the present generation chromosome population with a selected offspring chromosome if either;

(i) the selected offspring chromosome is more fit than the selected chromosome of the present generation chromosome population, or (ii) the selected offspring chromosome is as fit as the selected chromosome of the present generation chromosome population and the selected offspring chromosome has fewer expressed genes than the selected chromosome of the present generation chromosome population.

10. The method as set forth in claim 9, wherein:

the selected offspring chromosome is the most fit offspring chromosome and the selected chromosome of the present generation chromosome population is the least fit chromosome of the present generation chromosome population; and

the replacing is repeated until the most fit offspring chromosome is less fit than the least fit chromosome of the present generation chromosome population.

11. The method as set forth in claim 1, wherein the fitness criterion indicates the fitness of the sub-set of associated measurements specified by the expressed genes of each chromosome for classifying a group of measured subjects into two or more classifications, and the method further includes:

before producing of each successive generation chromosome population, introducing a selected level of simulated noise into values of measurements of the measured subjects.

12. The method as set forth in claim 1, wherein the fitness criterion indicates the fitness of the sub-set of associated measurements specified by the expressed genes of each chromosome for classifying a group of measured subjects into two or more classifications, and the method further includes:

before producing of each successive generation chromosome population, randomly or pseudorandomly splitting a set of measured subjects into a training group and a test group.

13. A medical diagnostic test for determining whether a medical subject has a pathology of interest, the method comprising:

classifying measurements of the medical subject using a medical diagnostic classifier determined by the method of claim 1, wherein the associated set of measurements characterize concentrations of organic macromolecules and the fitness criterion indicates fitness of the sub-set of associated measurements specified by the expressed genes of each chromosome for classifying medical subjects into a positive group having the pathology of interest and a negative group not having the pathology of interest.

14. The method as set forth in claim 13, wherein the associated set of measurements characterizing concentrations of organic macromolecules in a medical subject is one of:

a set of measurements of dots of a microarray processed using a biological sample taken from the medical subject, and

a set of signal levels of a mass spectrogram measured for a biological sample taken from the medical subject.

15. A method for determining a classifier, the method comprising:

producing a first generation chromosome population of chromosomes, each chromosome having a selected number of genes specifying a sub-set of an associated set of measurements;

computationally genetically evolving the genes of the chromosomes to produce successive generation chromosome populations, the producing of each successor generation chromosome population including;

generating offspring chromosomes from parent chromosomes of the present chromosome population by;

(i) filling genes of the offspring chromosome with gene values common to both parent chromosomes and (ii) filling remaining genes with gene values that are unique to one or the other of the parent chromosomes,

selectively mutating genes values of the offspring chromosomes that are unique to one or the other of the parent chromosomes without mutating gene values of the offspring chromosomes that are common to both parent chromosomes, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined using the sub-set of associated measurements specified by genes of that chromosome; and

selecting a classifier that uses the sub-set of associated measurements specified by genes of a chromosome identified by the genetic evolving.

16. The method as set forth in claim 15, wherein a mutation rate for the selective mutating of the gene values that are unique to one or the other of the parent chromosomes is greater than 5%.

17. The method as set forth in claim 15, wherein only a sub-set of the genes of each chromosome are expressed genes and the fitness of each chromosome is determined using the sub-set of the associated measurements specified by the expressed genes of that chromosome.

18. A medical diagnostic test for determining whether a medical subject has a pathology of interest, the method comprising:

classifying measurements of the medical subject using a medical diagnostic classifier determined by the method of claim 15, wherein the associated set of measurements characterize concentrations of organic macromolecules and the fitness quantifies effectiveness of the sub-set of associated measurements specified by genes of each chromosome for classifying a medical subjects into a positive group having the pathology of interest and a negative group not having the pathology of interest.

19. A method for determining a classifier, the method comprising:

producing a first generation chromosome population of chromosomes, each chromosome having a selected number of genes specifying a sub-set of an associated set of measurements;

computationally genetically evolving the genes of the chromosomes to produce successive generation chromosome populations, the producing of each successor generation chromosome population including;

introducing a selected level of simulated noise into values of the set of measurements for a group of subjects,

generating offspring chromosomes by mating chromosomes of the present chromosome population,

selectively mutating genes of the offspring chromosomes, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined respective to the values of the measurements of the group of subjects with the introduced simulated noise; and

selecting a classifier that uses the sub-set of associated measurements specified by genes of a chromosome identified by the genetic evolving.

20. A medical diagnostic test for determining whether a medical subject has a pathology of interest, the method comprising:

classifying measurements of the medical subject using a medical diagnostic classifier determined by the method of claim 19, wherein the associated set of measurements characterize concentrations of organic macromolecules and the fitness quantifies effectiveness of the sub-set of associated measurements specified by genes of each chromosome for classifying medical subjects into a positive group having the pathology of interest and a negative group not having the pathology of interest.

21. A genetic optimization method comprising:

computationally genetically evolving the genes of a chromosome population, the evolving including evolving a number of expressed genes in each chromosome and employing a fitness criterion evaluated without reference to unexpressed genes of each chromosome; and

selecting an optimized chromosome produced by the genetic evolving.

22. The method as set forth in claim 21, wherein the genetic evolving includes:

generating offspring chromosomes by mating selected parent chromosomes of the present chromosome population, each offspring chromosome having a number of expressed genes lying within a range defined by the number of expressed genes of the parent chromosomes from which that offspring chromosome is generated.

23. The method as set forth in claim 22, wherein the range defined by the number of expressed genes of the parent chromosomes includes at least one of:

(i) a value larger than a largest number of expressed genes in any of the parent chromosomes, and

(ii) a value smaller than a smallest number of expressed genes in any of the parent chromosomes.

24. The method as set forth in claim 21, wherein the genetic evolving includes:

generating an offspring chromosome by mating two selected parent chromosomes of the present chromosome population; and

selectively mutating genes of the offspring chromosome that are unique to one or the other of the two parent chromosomes without mutating genes of the offspring chromosome that are common to both parent chromosomes.

25. The method as set forth in claim 21, wherein the genetic evolving includes:

selecting chromosomes that survive into each successive generation using a selection criterion biased toward selecting chromosomes having a smaller number of expressed genes over chromosomes having a larger number of expressed genes.

26. The method as set forth in claim 21, wherein the genetic evolving includes:

generating offspring chromosomes by mating selected parent chromosomes of the parent chromosome population and introducing a select level of simulated noise into measurement values associated with the parent chromosomes.