EVOLUTIONARY CLUSTERING ALGORITHM

• US 20120016826A1
• Filed: 12/23/2009
• Published: 01/19/2012
• Est. Priority Date: 01/06/2009
• 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: Dimitrova, Nevenka, Behera, Narayan, Sinha, Shruti, Gupta, Rakesh, Geoncy, Ann
• Granted Patent: US 8,712,935 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• 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/30 Unsupervised data analysis

Abstract

The invention relates to selecting a set of candidate genes from a pool of genes. The method comprising receiving a set of gene data; arranging the set of gene data into a set of clusters with similar profiles by use of a clustering algorithm; and inputting the set of clusters into a genetic algorithm to select a set of candidate genes from the set of clusters. The method thus relates to hybrid between selection by clustering computation and selection by evolutionary computation. This hybrid is also referred to as an evolutionary clustering algorithm (ECA).

Claims

1. A computer-implemented method for selecting a set of candidate genes from a pool of genes, the method comprising:

receiving (10) a set of gene data;

arranging (1) the set of gene data into a set of clusters with similar profiles by use of a clustering algorithm, wherein the clustering algorithm employs an interdependence redundancy measure as distance measure; and

inputting (11) the set of clusters into a genetic algorithm to select a set of candidate genes from the set of clusters, wherein in each evolution of the genetic algorithm, the genes are reassigned to clusters by first determining the gene of each cluster having the highest multiple interdependence redundancy and assigned other genes of the cluster in accordance with the genes having the highest interdependence redundancy.

2. The method according to claim 1, wherein the set of gene data comprises a subset relating to a disease condition and a non-disease condition, and wherein the set of gene data has been pre-processed to remove gene data which are similar in the disease condition subset and in the non-disease condition subset.

3. The method according to claim 1, wherein a set of individuals are inputted into the genetic algorithm, and wherein each individual comprises a set of individual genes, the set of individual genes being generated by assigning to the corresponding gene from the gene data to the indices and the value at each index to the cluster to which the gene is assigned.

4. The method according to claim 3, wherein fitness of an individual is determined based on the multiple interdependence redundancy of the clusters.

5. The method according to claim 4, wherein in individual for the next generation is selected based on a roulette wheel selection routine, where the roulette wheel is constructed from the relative fitness of each individual.

6. The method according to claim 5, wherein the set of candidate genes is selected as the individual with the highest fitness.

7. The method according to claim 6, wherein the genes of the individual is further ranked in accordance with the highest multiple interdependence redundancy.

8. The computer-implemented method according to claim 1, wherein the gene data is obtained from microarray data, DNA-based array, differential DNA methylation arrays, chromatin immunoprecipitation on chip (ChIP) or methylation and gene number variations.

9. The method according to claim 1, wherein the candidate genes are biomarkers for the disease of cancer, the biomarkers being selected from or any combination of the biomarkers:

TGIF1, X90840, IGFBP4, HMHA1, CUL5, QSCN6 (QSOX1), COPS5, UBE4A, LOC440345, CCL4, ACAT1.

10. A computer program product, when in use on a computer, to cause a system to perform method of claim 1.

11. A system for selecting a set of candidate genes from a pool of genes, the system comprising:

a computing unit arranged to;

receiving a set of gene data;

cluster the set of gene data into a set of clusters with similar profiles by use of a clustering algorithm; and

evolve the set of clusters by a genetic algorithm to select a set of candidate genes from the set of clusters.