Regular PapersNo Access

P3M — POSSIBILISTIC MULTI-STEP MAXMIN AND MERGING ALGORITHM WITH APPLICATION TO GENE EXPRESSION DATA MINING

PRINCE Research Group (PRINCE stands for Pole de Recherche en INformatique du CEntre. It is a multi-disciplinary research group working in the fields of data mining, distributed computing, and intelligent networks.), Department of Computer Science, Faculty of Sciences of Monastir, University of Monastir, Monastir 5019, Tunisia

Search for more papers by this author

HECHMI SHILI

Search for more papers by this author

, and

BECHIR AYEB

Search for more papers by this author

https://doi.org/10.1142/S0218213009000263Cited by:0 (Source: Crossref)

Abstract

Gene expression data generated by DNA microarray experiments provide a vast resource of medical diagnostic and disease understanding. Unfortunately, the large amount of data makes it hard, sometimes impossible, to understand the correct behavior of genes. In this work, we develop a possibilistic approach for mining gene microarray data. Our model consists of two steps. In the first step, we use possibilistic clustering to partition the data into groups (or clusters). The optimal number of clusters is evaluated automatically from data using the Partition Information Entropy as a validity measure. In the second step, we select from each computed cluster the most representative genes and model them as a graph called a proximity graph. This set of graphs (or hyper-graph) will be used to predict the function of new and previously unknown genes. Benchmark results on real-world data sets reveal a good performance of our model in computing optimal partitions even in the presence of noise; and a high prediction accuracy on unknown genes.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

M. Ankerstet al., OPTICS: Ordering Points to Identify the Clustering Structure, Proc. of the ACM SIGMOD Int. Conf. on Management of Data (1999) pp. 49–60. Google Scholar
Wai-Ho Auet al., IEEE/ACM Trans. Comp. Bio. Bioinf. 2(2), 83 (2005). Web of Science, Google Scholar
P. Baldi and G. W. Hatfield , DNA Microarrays and Gene Expression : From Experiments to Data Analysis and Modeling ( Cambridge U. Press , Cambridge, USA , 2002 ) . Crossref, Google Scholar
J. C. Bezdek , Pattern Recognition with Fuzzy Objective Function Algorithms ( Plenum (NY) , 1981 ) . Crossref, Google Scholar
D. R. Bickel, Bioinformatics 19(7), 818 (2003), DOI: 10.1093/bioinformatics/btg092. Crossref, Web of Science, Google Scholar
M. Blatt, S. Wiseman and E. Domany, Phy. Rev. Letters 76(3254), 29 (1996). Google Scholar
K. Bryan, P. Cunningham and N. Bolshakova, IEEE Trans. Inform. Technol. Biomed. 10(3), 519 (2006), DOI: 10.1109/TITB.2006.872073. Crossref, Web of Science, Google Scholar
C. Hatzis and D. Page. Knowledge Discovery & Data Mining Cup, 2001. http://www.cs.wisc.edu/~dpage/kddcup2001 . Google Scholar
D. L. Davies and D. W. Bouldin, IEEE Trans. Pattern Anal. Machine Intell. 1(2), 224 (1979). Web of Science, Google Scholar
A. P. Dempster, N. M. Laird and D. B. Rubin, J. of the Roy. Stat. Soc-B 39(1), 1 (1977). Google Scholar
F. Divina and J. S. Aguilar-Ruiz, IEEE Trans. Knowledge Data Eng. 18(5), 590 (2006), DOI: 10.1109/TKDE.2006.74. Crossref, Web of Science, Google Scholar
B. Efron , The Jackknife, the Bootstrap, and Other Resampling Plans , Proc. of the CBMS-NSF Regional Conf. Series in Applied Mathematics 38 ( SIAM , 1982 ) . Google Scholar
M. B. Eisenet al., Proc. of the Nat. Aca. of Sc. 95(25), 14863 (1998), DOI: 10.1073/pnas.95.25.14863. Crossref, Web of Science, Google Scholar
G. Getz, E. Levine and E. Domany, Proc. of the Nat. Aca. of Sc. 97(22), 12079 (2000), DOI: 10.1073/pnas.210134797. Crossref, Web of Science, Google Scholar
R. Guthkeet al., Gene Expression Data Mining for Functional Genomics, Proc. of the European Symp. on Intelli. Techn. (2000) pp. 170–177. Google Scholar
J. Herrero, A. Valencia and J. Dopazo, Bioinformatics 17(2), 126 (2001), DOI: 10.1093/bioinformatics/17.2.126. Crossref, Web of Science, Google Scholar
A. Hinneburg and D. A. Keim, An Efficient Approach to Clustering in Large Multimedia Database with Noise, Proc. of the 4th Int. Conf. on Knowledge Discovery and Data Mining (1998) pp. 58–65. Google Scholar
D. Jiang, J. Pei and A. Zhang, DHC: A Density-Based Hierarchical Clustering Method for Time Series Gene Expression Data, Proc. of the 3rd IEEE Symp. on Bio-Informatics and Bio-Engineering (2003) pp. 393–400. Google Scholar
D. Jiang, C. Tang and A. Zhang, IEEE Trans. Knowledge Data Eng. 16(11), 1370 (2004). Crossref, Web of Science, Google Scholar
L. Kaufman and P. J. Rousseeuw , Finding Groups in Data: An Introduction to Cluster Analysis ( JWS, Inc. , NY, USA , 1990 ) . Crossref, Google Scholar
U. Kaymak, A Unified Approach for Practical Applications of Fuzzy Clustering, Proc. of 20th Belgium-Netherlands Conf. on Arti. Intell. (2000) pp. 101–108. Google Scholar
U. Kaymak and R. Babuska, Compatible Cluster Merging for Fuzzy Modeling, Proc. of the 4th IEEE International Conf. on Fuz. Sys.2 (1995) pp. 897–904. Google Scholar
E. Keedwell and A. Narayanan, IEEE/ACM Trans. Comp. Bio. Bioinf. 2(3), 231 (2005), DOI: 10.1109/TCBB.2005.40. Crossref, Web of Science, Google Scholar
G. Kowalski , Information Retrieval Systems: Theory and Implementation ( Kluwer, MA, USA , 1977 ) . Google Scholar
R. Krishnapuram and M. Keller, IEEE Trans. Fuzzy Syst. 1(2), 98 (1993), DOI: 10.1109/91.227387. Crossref, Web of Science, Google Scholar
M. Kumar, R. Stoll and N. Stoll, IEEE Trans. Fuzzy Syst. 14(2), 248 (2006), DOI: 10.1109/TFUZZ.2005.864081. Crossref, Web of Science, Google Scholar
L. Jinyan and L. Huiqing. Kent Ridge Bio-medical Data Set Repository, 2001. http://sdmc.lit.org.sg/GEDatasets . Google Scholar
C. G. Looney, Pat. Rec. 35(11), 2413 (2002), DOI: 10.1016/S0031-3203(01)00213-8. Crossref, Web of Science, Google Scholar
P. C. H. Maet al., IEEE Trans. Evol. Comput. 10(3), 296 (2006), DOI: 10.1109/TEVC.2005.859371. Crossref, Web of Science, Google Scholar
S. C. Madeira and A. L. Oliveira, IEEE/ACM Trans. Comp. Bio. Bioinf. 1(1), 24 (2004), DOI: 10.1109/TCBB.2004.2. Crossref, Web of Science, Google Scholar
G. J. McLachlan, R. W. Bean and D. Peel, Bioinformatics 18(3), 413 (2002), DOI: 10.1093/bioinformatics/18.3.413. Crossref, Web of Science, Google Scholar
N. R. Pal and J. C. Bezdek, IEEE Trans. Fuzzy Syst. 3(2), 370 (1995), DOI: 10.1109/91.413225. Crossref, Web of Science, Google Scholar
Nikhil R. Pal, James M. Keller and James C. Bezdek, IEEE Trans. Fuzzy Syst. 13(4), 517 (2005), DOI: 10.1109/TFUZZ.2004.840099. Crossref, Web of Science, Google Scholar
P. A. Ralf-Herwiget al., Genome Research 9(11), 1093 (1999). Crossref, Web of Science, Google Scholar
L. B. Romdhane, B. Ayeb and S. Wang, Int. J. of Neur. Sys. 12(2), 149 (2002). Link, Google Scholar
K. Rose, Proc. of the IEEE 86(11), 2210 (1998), DOI: 10.1109/5.726788. Crossref, Web of Science, Google Scholar
R. Shamir and R. Sharan, CLICK: A Clustering Algorithm for Gene Expression Analysis, Proc. 8th Int. Conf. on Intelligent Systems for Molecular Biology (2000) pp. 307–316. Google Scholar
C. E. Shannon, Bell System Tech. J. 27, 623 (1948). Crossref, Web of Science, Google Scholar
F. D. Smetet al., Bioinformatics 18(5), 735 (2002). Crossref, Web of Science, Google Scholar
H. Sun, S. Wang and Q. Jiang, Pat. Rec. 37(10), 2027 (2004), DOI: 10.1016/j.patcog.2004.03.012. Crossref, Web of Science, Google Scholar
C. Tanget al., Interrelated Two-Way Clustering: An Unsupervised Approach for Gene Expression Data Analysis, Proc. of the 2nd IEEE Int. Symp. Bioinformatics and Bioengineering (2001) pp. 41–48. Google Scholar
A. Tefferiet al., Mayo Clinic Proc. 77, 927 (2002), DOI: 10.4065/77.9.927. Crossref, Web of Science, Google Scholar
S. Tomidaet al., Bioinformatics 18(8), 1073 (2002), DOI: 10.1093/bioinformatics/18.8.1073. Crossref, Web of Science, Google Scholar
J. T. Tou and R. C. Gonzalez , Pattern Recognition Principles ( Add.-Wes. , MA, USA , 1974 ) . Google Scholar
Huai-Kuang Tsaiet al., IEEE Trans. Inform. Technol. Biomed. 8(2), 69 (2004), DOI: 10.1109/TITB.2004.826713. Crossref, Web of Science, Google Scholar
University of Pittsburgh. UPITT Cancer Gene Expression Data Set Link Database. http://bioinformatics2.pitt.edu/index.html . Google Scholar
Web site. Gepas software. http://transcriptome.ens.fr/gepas/ . Google Scholar
S. Wuet al., IEEE Trans. Inform. Technol. Biomed. 8(1), 5 (2004), DOI: 10.1109/TITB.2004.824724. Crossref, Web of Science, Google Scholar
J. Yanget al., δClusters: Capturing Subspace Correlation in a Large Data Set, Proc. 18th IEEE Int. Conf. on Data Engineering (IEEE Computer Society, 2002) pp. 517–528. Google Scholar
K. Y. Yeunget al., Bioinformatics 17(10), 977 (2001), DOI: 10.1093/bioinformatics/17.10.977. Crossref, Web of Science, Google Scholar
X. Yinget al., Int. J. of App. Reaso. 40, 109 (2005). Web of Science, Google Scholar