Methods for optimizing and using medical diagnostic classifiers based on genetic algorithms

• US 8,798,937 B2
• Filed: 02/01/2005
• Issued: 08/05/2014
• Est. Priority Date: 02/10/2004
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Schaffer, J. David, Siimpson, Mark R.
• Primary Examiner(s): Whaley, Pablo S
• Application Number:
  US10/597,767
• Publication Number:
  US 20070172828A1
• Time in Patent Office: 3,472 Days
• Field of Search: None
• US Class Current: 702/20
• 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 optimizing medical diagnostic classifiers using a genetic algorithm, the method comprising:

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generation chromosome population comprising chromosomes, each chromosome represented as chromosomal bit-strings;

assigning an index value to each gene of an ordered set of genes, wherein each index indexes a measurement of the set of measurements, and each gene of the ordered set of genes is represented as genetic bit-strings;

assigning an ordinal position value to an expressed sub-set-size gene that separates expressed genes from unexpressed genes in the ordered set of genes;

generating a fitness criterion that qualifies effectiveness of the expressed genes of each chromosome for identifying the cancer in the set of learning cases, the fitness criterion being evaluated without reference to the unexpressed genes of the chromosome to produce successive generation chromosome populations, wherein computational genetic evolving is performed by a computing system, the computational genetic evolving including;

mating pairs of parent chromosomes of the present generation chromosome population to generate offspring chromosomes,

for each offspring chromosome, computing a value for the fitness criterion using a classifier defined by the measurements specified by the expressed genes of the offspring chromosome without reference to the unexpressed genes of the offspring chromosome and trained on the set of learning cases, and

selecting the next generation chromosome population based on the computed values of the fitness criterion; and

selecting a classifier corresponding to a most it chromosome identified by genetic evolving.

2. The method as set forth in claim 1, 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 each offspring chromosome from two parent chromosomes of the present generation 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.

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

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.

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

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.

5. The method as set forth in claim 4, 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.

6. The method as set forth in claim 1, wherein the method further includes:

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

7. A method for classifying whether a medical subject has cancer using a classifier optimized using a genetic algorithm, the method comprising:

generating a medical diagnostic classifier by performing a method including;

training the classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data characterizing concentrations of organic macromolecules in the human test subjects;

producing a first generation chromosome population comprising chromosomes, each chromosome represented as chromosomal bit-strings;

assigning an index value to each gene of an ordered set of genes, wherein each index indexes a measurement of the set of measurements, and each gene of the ordered set of genes is represented as generic bit-strings;

assigning an ordinal position value to an expressed sub-set-size gene that separates expressed genes from unexpressed genes in the ordered set of genes;

generating a fitness criterion that quantifies effectiveness of the expressed genes of each chromosome for classifying the human test subjects into either a positive group having cancer or a negative group not having cancer, the fitness criterion being evaluated without reference to the unexpressed genes of the chromosome to produce successive generation chromosome populations, wherein computational genetic evolving is performed by a computing system, the computational genetic evolving including;

mating pairs of parent chromosomes of the present generation chromosome population to generate offspring chromosomes,

for each offspring chromosome, computing a value for the fitness criterion using a classifier defined by the measurements specified by the expressed genes of the offspring chromosome without reference to the unexpressed genes of the offspring chromosome and trained on the set of learning cases, and

selecting the next generation chromosome population based on the computed values of the fitness criterion; and

selecting a classifier corresponding to a most fit chromosome;

wherein the classifier corresponding to a most fit chromosome is selected as the medical diagnostic classifier; and

classifying measurement data for the set of measurements acquired from the medical subject using the medical diagnostic classifier implemented by a computer to classify the medical subject as to whether the medical subject has cancer.

8. The method as set forth in claim 7, wherein the 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.

9. A method for optimizing medical diagnostic classifiers using a genetic algorithm, the method comprising:

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generation chromosome population of chromosomes, each chromosome represented as chromosomal bit-strings;

generating successive generation chromosome populations by;

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,

after the selective mutating, training a classifier for each offspring chromosome that uses a sub-set of the set of measurements,

generating a fitness criterion that quantifies effectiveness of the classifier for identifying cancer in the set of learning cases, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined using the trained classifier of that chromosome and measured by the fitness criterion; and

selecting the trained classifier corresponding to a most fit chromosome.

10. The method as set forth in claim 9, 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%.

11. The method as set forth in claim 9, wherein only a sub-set of the genes of each chromosome are expressed genes and the classifier is trained using the sub-set of the associated measurements specified by the expressed genes of that chromosome.

12. A method for classifying whether a medical subject has cancer, the method comprising:

generating a medical diagnostic classifier by performing a method including;

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generation chromosome population of chromosomes, each chromosome represented as chromosomal bit-strings;

generating successive generation chromosome populations by;

generating offspring chromosomes from patent 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,

after the selective mutating, training a classifier for each offspring chromosome that uses a sub-set of the set of measurements,

generating a fitness criterion that quantifies effectiveness of the classifier for identifying cancer in the set of learning cases, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined using the trained classifier of that chromosome and measured by the fitness criterion; and

selecting the trained classifier corresponding to a most fit chromosome,

wherein the trained classifier corresponding to a most fit chromosome is selected as the medical diagnostic classifier; and

classifying measurement data for the set of measurements acquired from the medical subject using the medical diagnostic classifier implemented by a computer to classify the medical subject as to whether the medical subject has cancer.

13. A method for optimizing medical diagnostic classifiers using a genetic algorithm, the method comprising:

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generation chromosome population of chromosomes, each chromosome represented as chromosomal bit-strings;

generating successive generation chromosome populations by;

introducing a selected level of simulated noise into the measurement data for the set of measurements acquired from the pool of human subjects,

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

selectively mutating genes of the offspring chromosomes,

after the selective mutating, training a classifier for each offspring chromosome that uses a sub-set of the set of measurements,

generating a fitness criterion that quantifies effectiveness of the classifier for identifying cancer in the set of learning cases with the introduced simulated noise, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined using the trained classifier of that chromosome and measured by the fitness criterion respective to the measurement data for the set of measurements acquired from the pool of human subjects with the introduced simulated noise; and

selecting the trained classifier corresponding to a most fit chromosome;

wherein the selecting is performed by a computing system.

14. A method for classifying whether a medical subject has cancer using a classifier optimized using a genetic algorithm, the method comprising:

generating a medical diagnostic classifier by performing a method including;

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generation chromosome population of chromosomes, each chromosome represented as chromosomal bit-strings;

generating successive generation chromosome populations by;

introducing a selected level of simulated noise into the measurement data for the set of measurements acquired from the pool of human subjects,

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

selectively mutating genes of the offspring chromosomes,

after the selective mutating, training a classifier for each offspring chromosome that uses a sub-set of the associated set of measurements,

generating a fitness criterion that quantifies effectiveness or the classifier for identifying cancer in the set of learning cases with the introduced simulated noise, and

updating the chromosome population with offspring chromosomes based on a fitness of each chromosome determined using the trained classifier of that chromosome and measured by the fitness criterion respective to the measurement data for the set of measurements acquired from the pool of human subjects with the introduced simulated noise; and

selecting the trained classifier corresponding to a most fit chromosome;

wherein the selecting is performed by a computing system and wherein the trained classifier corresponding to a most fit chromosome is selected as the medical diagnostic classifier; and

classifying measurement data for the set of measurements acquired from the medical subject using the medical diagnostic classifier implemented by a computer, to classify the medical subject as to whether the medical subject has cancer.

15. A method for optimizing medical diagnostic classifiers using a genetic algorithm, the method comprising:

training a classifier via a set of learning cases, the learning cases comprising measurement data for a set of measurements acquired from a pool of human test subjects some of whom have cancer and some of whom do not have cancer, the measurement data comprising measured concentrations of organic macromolecules;

producing a first generating chromosome population comprising chromosomes, each chromosome represented as bit-strings;

assigning an index value to each gene of an ordered set of genes, wherein each index indexes a measurement of the set of measurements, and each gene of the ordered set of genes is represented as generic bit-strings;

wherein the producing step includes;

assigning an ordinal position value to a number of expressed genes;

generating a fitness criterion quantifying effectiveness of the expressed genes of each chromosome for identifying cancer in the set of learning cases, the fitness criterion being evaluated without reference to unexpressed genes of each chromosome, and

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; and

selecting a most fit chromosome as measured by the fitness criterion;

wherein the selecting is performed by a computing system.

16. The method as set forth in claim 15, 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.

17. The method as set forth in claim 15, 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.