Back to search

Lethbridge, Alta. : University of Lethbridge, Deptartment of Mathematics and Computer Science, 2008

Approximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformatics

Abstract

dc:description.abstract

Clusters in protein interaction networks can potentially help identify functional relationships among proteins. We study the clustering problem by modeling it as graph cut problems. Given an edge weighted graph, the goal is to partition the graph into a prescribed number of subsets obeying some capacity constraints, so as to maximize the total weight of the edges that are within a subset. Identification of a dense subset might shed some light on the biological function of all the proteins in the subset. We study integer programming formulations and exhibit large integrality gaps for various formulations. This is indicative of the difficulty in obtaining constant factor approximation algorithms using the primal-dual schema. We propose three approximation algorithms for the problem. We evaluate the algorithms on the database of interacting proteins and on randomly generated graphs. Our experiments show that the algorithms are fast and have good performance ratio in practice.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Deptartment of Mathematics and Computer Science, 2008
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Choudhury, Salimur Rashid
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Gaur, Daya

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/774

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Choudhury, Salimur Rashid; University of Lethbridge. Faculty of Arts and Science. Approximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformatics. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Deptartment of Mathematics and Computer Science, 2008, 2008. https://hdl.handle.net/10133/774