Clique-finding tool for Detecting Gene Clusters

Abstract

De ning relationships between species is a fundamental problem in bioinformatics. One of the ways to de ne relationships is to detect gene clusters, and can be formulated as a combinatorial problem called Approximate Gene Cluster Discovery Problem (AGCDP). Graph concepts have been applied to several genomic studies. AGCDP can be reduced to optimization problems in graph, speci cally the Minimum Weight t-Partite Clique Problem (MWtCP). The goal of MWtCP is to create a t-partite graph and to nd a t-star with minimum weight, which is used to approximate a t-clique. Clustar is a tool that applies an algorithm which solves the MWtCP for detecting gene clusters. It allows the user to detect gene clusters using three methods: approximate gene clustering, exact gene clustering (using GPU), and exact gene clustering (without using GPU). Clustar is able to produce candidate gene clusters and its alignment among the genomes, as well as the graph representation and the adjacency matrix produced from the generated graph. To verify the validity of the results produced by Clustar, a dataset containing homologous genes from 30 $gamma$-proteobacterial genomes was processed using Clustar and other algorithms such as The Row's Subset of Symmetric Matrix (RSSM) and hierarchical clustering. Several gene clusters were found common across these three algorithms using di erent gene cluster sizes. Another dataset was used containing genes from E. coli and B. subtilis where several gene-groups have been established already. Clustar was able to produce candidate gene clusters that matched these gene-groups, using di erent gene cluster sizes.