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

Simple item page
dc.contributor.authorChoudhury, Salimur Rashid
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2009-10-09T20:49:06Z
dc.date.available2009-10-09T20:49:06Z
dc.date.issued2008
dc.degree.levelMasters
dc.descriptionxiii, 71 leaves : ill. ; 29 cm.en
dc.description.abstractClusters 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.en
dc.identifier.urihttps://hdl.handle.net/10133/774
dc.language.isoen_USen
dc.publisherLethbridge, Alta. : University of Lethbridge, Deptartment of Mathematics and Computer Science, 2008en
dc.publisher.departmentMathematics and Computer Scienceen
dc.publisher.facultyArts and Scienceen
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en
dc.subjectCluster analysis -- Computer programsen
dc.subjectProtein-protein interactions -- Data processingen
dc.subjectProteins -- Research -- Data processingen
dc.subjectGraph algorithmsen
dc.subjectBioinformaticsen
dc.subjectDissertations, Academicen
dc.titleApproximation algorithms for a graph-cut problem with applications to a clustering problem in bioinformaticsen
dc.typeThesisen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
CHOUDHURY_SALIMUR_MSC_2008.pdf
Size:
314.16 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.88 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses