World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Parallel Local Search Algorithm for Clustering Large Biological Networks

    Clustering is an effective technique that can be used to analyze and extract useful information from large biological networks. Popular clustering solutions often require user input for several algorithm options that can seem very arbitrary without experimentation. These algorithms can provide good results in a reasonable time period but they are not above improvements. We present a local search based clustering algorithm free of such required input that can be used to improve the cluster quality of a set of given clusters taken from any existing algorithm or clusters produced via any arbitrary assignment. We implement this local search using a modern GPU based approach to allow for efficient runtime. The proposed algorithm shows promising results for improving the quality of clusters. With already high quality input clusters we can achieve cluster rating improvements upto to 33%.

    References

    • 1. M. P. Brown, W. N. Grundy, D. Lin, N. Cristianini, C. W. Sugnet, T. S. Furey, M. Ares, and D. Haussler, “ Knowledge-based analysis of microarray gene expression data by using support vector machines,” Proceedings of the National Academy of Sciences, Vol. 97, No. 1, pp. 262–267, 2000. Google Scholar
    • 2. D. K. Slonim, “ From patterns to pathways: Gene expression data analysis comes of age,” Nature genetics, Vol. 32, p. 502, 2002. Crossref, ISIGoogle Scholar
    • 3. A. H. Y. Tong, G. Lesage, G. D. Bader, H. Ding, H. Xu, X. Xin, J. Young, G. F. Berriz, R. L. Brost, M. Chang, et al., “ Global mapping of the yeast genetic interaction network,” Science, Vol. 303, No. 5659, pp. 808–813, 2004. Crossref, ISIGoogle Scholar
    • 4. B. Andreopoulos, A. An, X. Wang, and M. Schroeder, “ A roadmap of clustering algorithms: Finding a match for a biomedical application,” Briefings in Bioinformatics, Vol. 10, No. 3, pp. 297–314, 2009. Crossref, ISIGoogle Scholar
    • 5. P. D’haeseleer, “ How does gene expression clustering work?,” Nature Biotechnology, Vol. 23, No. 12, pp. 1499–1502, 2005. Crossref, ISIGoogle Scholar
    • 6. M. Shafin, K. Kabir, I. Ridwan, T. T. Anannya, R. S. Karim, M. M. Hoque, and M. S. Rahman, “ Impact of heuristics in clustering large biological networks,” Computational Biology and Chemistry, Vol. 59, pp. 28–36, 2015. Crossref, ISIGoogle Scholar
    • 7. C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, “ A min-max cut algorithm for graph partitioning and data clustering,” in Proceedings IEEE International Conference on Data Mining, 2001. ICDM 2001, pp. 107–114, IEEE, 2001. Google Scholar
    • 8. P. Chopra, J. Kang, J. Yang, H. Cho, H. S. Kim, and M.-G. Lee, “ Microarray data mining using landmark gene-guided clustering,” BMC Bioinformatics, Vol. 9, No. 1, p. 92, 2008. CrossrefGoogle Scholar
    • 9. S. Choudhury, Approximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformatics. PhD thesis, Lethbridge, Alta.: University of Lethbridge, Department of Mathematics and Computer Science, 2008. Google Scholar
    • 10. H. Saran and V. V. Vazirani, “ Finding k cuts within twice the optimal,” SIAM Journal on Computing, Vol. 24, No. 1, pp. 101–108, 1995. Crossref, ISIGoogle Scholar
    • 11. S. Choudhury, D. R. Gaur, and R. Krishnamurti, “ An approximation algorithm for max k-uncut with capacity constraints,” Optimization, Vol. 61, No. 2, pp. 143–150, 2012. Crossref, ISIGoogle Scholar
    • 12. G. Coccimiglio and S. Choudhury, “ A local search algorithm for clustering large biological networks,” in Proceedings IEEE International Conference on Bioinformatics and Computational Biology, pp. 73–78, ISCA, 2017. Google Scholar
    • 13. C. C. Aggarwal and C. K. Reddy, Data Clustering: Algorithms and Applications, CRC Press, 2013. CrossrefGoogle Scholar
    • 14. P. Jiang and M. Singh, “ SPICi: A fast clustering algorithm for large biological networks,” Bioinformatics, Vol. 26, No. 8, pp. 1105–1111, 2010. Crossref, ISIGoogle Scholar
    • 15. S. M. Van Dongen, “Graph clustering by flow simulation,” 2001. Google Scholar
    • 16. A. D. King, N. Pržulj, and I. Jurisica, “ Protein complex prediction via cost-based clustering,” Bioinformatics, Vol. 20, No. 17, pp. 3013–3020, 2004. Crossref, ISIGoogle Scholar
    • 17. A. D. King, Graph Clustering with Restricted Neighbourhood Search, University of Toronto, Toronto, 2004. Google Scholar
    • 18. S. Brohee and J. Van Helden, “ Evaluation of clustering algorithms for protein-protein interaction networks,” BMC Bioinformatics, Vol. 7, No. 1, p. 488, 2006. CrossrefGoogle Scholar
    • 19. G. D. Bader and C. W. Hogue, “ An automated method for finding molecular complexes in large protein interaction networks,” BMC Bioinformatics, Vol. 4, No. 1, p. 2, 2003. CrossrefGoogle Scholar
    • 20. A. Arbelaez and P. Codognet, “ A GPU implementation of parallel constraint-based local search,” in Proceedings of Distributed and Network-Based Processing, pp. 648–655, IEEE, 2014. Google Scholar
    • 21. T. V. Luong, L. N. Melab, and E. Talbi, Local Search Algorithms on Graphics Processing Units. A Case Study: The Permutation Perceptron Problem, pp. 264–275. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. Google Scholar
    • 22. A. Munawar, M. Wahib, M. Munetomo, and K. Akama, “ Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework,” Genetic Programming and Evolvable Machines, Vol. 10, No. 4, p. 391, 2009. Crossref, ISIGoogle Scholar
    • 23. A. Delévacq, P. Delisle, and M. Krajecki, “ Parallel GPU implementation of iterated local search for the travelling salesman problem,” Learning and Intelligent Optimization, pp. 372–377, 2012. CrossrefGoogle Scholar
    • 24. J. Fosin, D. Davidović, and T. Carić, “ A GPU implementation of local search operators for symmetric travelling salesman problem,” PROMET-Traffic&Transportation, Vol. 25, No. 3, pp. 225–234, 2013. Crossref, ISIGoogle Scholar
    • 25. M. G. A. Verhoeven and E. H. L. Aarts, “ Parallel local search,” Journal of Heuristics, Vol. 1, pp. 43–65, September 1995. CrossrefGoogle Scholar
    • 26. B. Breitkreutz, C. Stark, T. Reguly, L. Boucher, A. Breitkreutz, M. Livstone, R. Oughtred, D. H. Lackner, J. Bähler, V. Wood, et al.., “ The biogrid interaction database: 2008 update,” Nucleic Acids Research, Vol. 36, Suppl. 1, pp. D637–D640, 2008. Google Scholar
    • 27. L. J. Jensen, J. Lagarde, C. Von Mering, and P. Bork, “ Arrayprospector: A web resource of functional associations inferred from microarray expression data,” Nucleic Acids Research, Vol. 32, Suppl. 2, pp. W445–W448, 2004. CrossrefGoogle Scholar
    • 28. J. Song and M. Singh, “ How and when should interactome-derived clusters be used to predict functional modules and protein function?,” Bioinformatics, Vol. 25, No. 23, pp. 3143–3150, 2009. Crossref, ISIGoogle Scholar