Algorithmic and Complexity Issues of Three Clustering Methods in Microarray Data Analysis

1. Alizadeh, A., et al.: Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling. Nature 403, 503–510 (2000)

   Article  Google Scholar 

2. Ausiello, G., et al.: Complexity and Approximation. Springer, Heidelberg (1999)

   Book  MATH  Google Scholar 

3. Ben-Dor, A., Yakhini, Z.: Clustering gene expression patterns. In: Proc. RECOMB 1999, pp. 33–42 (1999)

   Google Scholar 

4. Ben-Dor, A., Chor, B., Karp, R., Yakhini, Z.: Discovering local structure in gene expression data: The order-preserving submatrix problem. In: Proceedings of RECOMB 2002, pp. 49–57 (2002)

   Google Scholar 

5. Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithm for tiling and packing problems with rectangles. J. Alg. 41, 443–470 (2001)

   Article  MathSciNet  MATH  Google Scholar 

6. Chen, Y., Dougherty, E., Bitter, M.: Ratio-based decisions and the quantitative analysis of cDNA microarray images. J. Biomed. Optics 2, 364–374 (1997)

   Article  Google Scholar 

7. Cheng, Y., Church, G.: Biclustering of expression data. In: Proceedings of ISMB 2000, pp. 93-103 (2000)

   Google Scholar 

8. Cormen, T.H., et al.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)

   MATH  Google Scholar 

9. Eisen, M.B., et al.: Clustering Analysis and display of genome-wide expression pattern. Proc. Natl. Amer. Sci. 95, 14863–14868 (1998)

   Article  Google Scholar 

10. Garey, M.R., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)

    MATH  Google Scholar 

11. Hartuv, E., et al.: An algorithm for clustering cDNAs for gene expression analysis. In: Proceedings of Recomb 1999, pp. 188–197 (1999)

    Google Scholar 

12. Hedenfalk, I., et al.: Gene-expression profiles in hereditary breast cancer. New England Journal of Medicine 344, 539–548 (2001)

    Article  Google Scholar 

13. Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Co. (1995)

    Google Scholar 

14. Kolda, T.G., O’Leary, D.P.: A semidiscrete matrix decomposition for latent semantic indexing in information retrieval. ACM Trans. on Information Systems 16, 322–346 (1998)

    Article  Google Scholar 

15. Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston Inc. (1976)

    MATH  Google Scholar 

16. Liu, J., Yang, J., Wang, W.: Biclustering in gene expression data by tendency. In: Proceedings of CSB 2004, pp. 182–193 (2004)

    Google Scholar 

17. Lazzeroni, L., Owen, A.: Plaid Models for Gene Expression Data. Statistica Sinica 12, 61–86 (2002); See http://www-stat.stanford.edu/~owen for more about Plaid model.

    MathSciNet  MATH  Google Scholar 

18. Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401, 788–791 (1999)

    Article  Google Scholar 

19. Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics 131, 651–654 (2003)

    Article  MathSciNet  MATH  Google Scholar 

20. Tamayo, P., et al.: Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation. Proc. Natl. Acad. Sci. 96, 2907–2912 (1999)

    Article  Google Scholar 

21. Troyanskaya, O., et al.: Missing value estimation methods for DNA microarrays. Bioinformatics 17, 520–525 (2001)

    Article  Google Scholar 

22. Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual STOC, pp. 253–264 (1978)

    Google Scholar 

23. Zhang, L., Zhu, S.: Complexity Study on Two Clustering Problems. In: Proceedings of the Annual Inter. Symposium on Alg. and Comput., pp. 660–669 (2001)

    Google Scholar 

24. Zhang, L., Zhu, S.: A new approach to clustering gene expression data. In: Proceedings of IEEE Symposium on Bioinformatics, pp. 268–275 (2002)

    Google Scholar 

Download references