Abstract
Based on the general framework of logical analysis of data, we develop a probe design method for selecting short oligo probes for genotyping applications in this paper. When extensively tested on genomic sequences downloaded from the Lost Alamos National Laboratory and the National Center of Biotechnology Information websites in various monospecific and polyspecific in silico experimental settings, the proposed probe design method selected a small number of oligo probes of length 7 or 8 nucleotides that perfectly classified all unseen testing sequences. These results well illustrate the utility of the proposed method in genotyping applications.
This paper is dedicated to the life and memory of Dr. Peter L. Hammer (December 23, 1936 - December 27, 2006), the inventor of LAD and an OR giant.
This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD)(KRF-2005-003-D00445).
Chapter PDF
Similar content being viewed by others
References
Stears, R., Martinsky, T., Schena, M.: Trends in microarray analysis. Nature Medicine 9(1), 140–145 (2003)
Eom, J.H., Park, S.B., Zhang, B.T.: Genetic mining of dna sequence structures for effective classification of the risk types of human papillomavirus (hpv). In: Pal, N.R., Kasabov, N., Mudi, R.K., Pal, S., Parui, S.K. (eds.) ICONIP 2004. LNCS, vol. 3316, pp. 1334–1343. Springer, Heidelberg (2004)
Heller, R., Schena, M., Chai, A., Shalon, D., Bedilion, T., Gilmore, J., Woolley, D., Davis, R.: Discovery and analysis of inflammatory disease-related genes using cdna microarrays. Proceedings of the National Academy of Sciences 94, 2150–2155 (1997)
Liu, C.H., Ma, W.L., Shi, R., Ou, Y.Q., Zhang, B., Zheng, W.L.: Possibility of using dna chip technology for diagnosis of human papillomavirus. Journal of Biochemistry and Molecular Biology 36(4), 349–353 (2003)
Lee, Y., Lee, C.K.: Classification of multiple cancer types by multicategory support vector machines using gene expression data. Bioinformatics 19(9), 1132–1139 (2003)
Sengupta, S., Onodera, K., Lai, A., Melcher, U.: Molecular detection and identification of influenza viruses by oligonucleotide microarray hybridization. Journal of Clinical Microbiology 41(10), 4542–4550 (2003)
Vernet, G.: Dna-chip technology and infectious diseases. Virus Research 82, 65–71 (2002)
Wang, D., Coscoy, L., Zylberberg, M., Avila, P., Boushey, H., Ganem, D., DeRisi, J.: Microarray-based detection and genotyping of viral pathogens. PNAS 99(24), 15687–15692 (2002)
Li, F., Stormo, G.: Selection of optimal dna oligos for gene expression arrays. Bioinformatics 17(11), 1067–1076 (2001)
Borneman, J., Chrobak, M., Vedova, G., Figueroa, A., Jiang, T.: Probe selection algorithms with applications in the analysis of microbial communities. Bioinformatics 17(Suppl. 1), S39–S48 (2001)
Rahmann, S.: Fast large scale oligonucleotide selection using the longest common factor approach. Journal of Bioinformatics and Computational Biology 1(2), 343–361 (2003)
Klau, G., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Optimal robust non-unique probe selection using integer linear programming. Bioinformatics 20 (Suppl. 1), i186–i193 (2004)
Boros, E., Hammer, P., Ibaraki, T., Kogan, A., Mayoraz, E., Muchnik, I.: An implementation of logical analysis of data. IEEE Transactions on Knowledge and Data Engineering 12, 292–306 (2000)
Megiddo, N.: On the complexity of polyhedral separability. Discrete and Computational Geometry 3, 325–337 (1988)
Ryoo, H., Jang, I.Y.: Milp approach to pattern generation in logical analysis of data. Machine Learning, submitted (2005)
Altschul, S., Gish, W., Miller, W., Myers, E., Lipman, D.: Basic local alignment search tool. Journal of Molecular Biology 215, 403–410 (1990)
Wang, X., Seed, B.: Selection of oligonucleotide probes for protein coding sequences. Bioinformatics 19(7), 796–802 (2003)
Cortes, C., Vapnik, V.: Support vector networks. Machine Learning 20, 273–297 (1995)
Ullman, J.: Pattern Recognition Techniques. Crane, London (1973)
Vapnik, V.: Statistical Learning Theory. Wiley Interscience, Hoboken (1998)
Hammer, P.: Partially defined boolean functions and cause-effect relationships. In: Proceedings of the International Conference on Multi-Attribute Decision Making Via OR-Based Expert Systems (1986)
Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set covering problem. Operations Research 47(5), 730–743 (1999)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience Series I Discrete Mathematics and Optimization. Wiley, New York (1988)
Muñoz, N., Bosch, F., de Sanjosé, S., Herrero, R., Castellsagué, X., Shah, K., Snijders, P., Meijer, C.J.L.M., for the International Agency for Research on Cancer Multicenter Cervical Cancer Study Group: Epidemiologic classification of human papillomavirus types associated with cervical cancer. The New England Journal of Medicine 348(6), 518–527 (2003)
Bosch, F., Lorincz, A., Muñoz, N., Meijer, C., Shah, K.: The causal relation between human papillomavirus and cervical cancer. Journal of Clinical Pathology 55, 244–265 (2002)
McFadden, S., Schumann, L.: The role of human papillomavirus in screening for cervical cancer. Journal of the American Academy of Nurse Practitioners 13, 116–125 (2001)
Park, S.B., Hwang, S.H., Zhang, B.T.: Classification of the risk types of human papillomavirus by decision trees. In: Liu, J., Cheung, Y.-m., Yin, H. (eds.) IDEAL 2003. LNCS, vol. 2690, pp. 540–544. Springer, Heidelberg (2003)
Snijder, E., Bredenbeek, P., Dobbe, J., Thiel, V., Ziebuhr, J., Poon, L., Guan, Y., Rozanov, M., Spaan, W., Gorbalenya, A.: Unique and conserved features of genome and proteome of sars-coronavirus, an early split-off from the coronavirus group 2 lineage. Journal of Molecular Biology 331, 991–1004 (2003)
Koopmans, M., Wilbrink, B., Conyn, M., Natrop, G., van der Nat, H., Vennema, H., Meijer, A., van Steenbergen, J., Fouchier, R., Osterhaus, A., Bosman, A.: Transmission of h7n7 avian influenza a virus to human beings during a large outbreak in commercial poultry farms in the netherlands. Lancet 363, 587–593 (2004), http://www.thelancet.com
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Kim, K., Ryoo, H.S. (2007). Selecting Genotyping Oligo Probes Via Logical Analysis of Data . In: Kobti, Z., Wu, D. (eds) Advances in Artificial Intelligence. Canadian AI 2007. Lecture Notes in Computer Science(), vol 4509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72665-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-72665-4_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72664-7
Online ISBN: 978-3-540-72665-4
eBook Packages: Computer ScienceComputer Science (R0)