Project abstract for group karypisg

Scalable Algorithms for Graph Partitioning, Data Mining, Bioinformatics, and Cheminformatics

The Karypis group is developing computational techniques in a number of fields. 

Their research for developing algorithms for graph partitioning focuses on the following areas:

  • Develop memory-efficient formulations of the multilevel graph partitioning paradigm.
  • Develop hybrid parallel formulations of parallel graph partitioning that combines shared-memory and distributed memory.


Research in developing computational techniques in computational biology, bioinformatics and cheminformatics focuses on the following areas:

  • Developing better machine learning algorithms based on support vector machines by designing kernels functions that capture the characteristics of proteins and chemical compounds and improving their scalability.
  • Developing better scoring methods for sequence alignment, sequence-structure search methods, and statistically derived potential functions that are designed to capture the sequence-structure conservation present in protein sequences.
  • Developing better feature extraction algorithms for chemical compounds that utilize topological and geometric substructures.
  • Developing better machine learning algorithms for chemical compound classification, structure-activity relationship (SAR) modeling, target fishing and target hopping.
  • Developing machine learning and data mining algorithms for compound synthesizability prediction and compound library design.


Research in data mining focuses on:

  • Developing efficient and novel algorithms for recommender systems with constraints.
  • Developing better collaborative filtering algorithms that utilize sparse linear models and take into account social network information.
  • Developing pattern discovery algorithms for mining dynamic complex relational graphs.


A bibliography of this group’s publications acknowledging MSI is attached.