Search for a star: Approximate gene cluster discovery problem (AGCDP) as minimization problem on graph
College
College of Computer Studies
Department/Unit
Computer Science
Document Type
Archival Material/Manuscript
Publication Date
2012
Abstract
Finding gene clusters in genomes is an essential process in establishing relationship among organisms. Gene clusters may express functional dependencies among genes and may give insight into expression of specific traits. The problem of finding gene clusters among several genomes is referred to as Gene Cluster Discovery and several models has already been formulated for its definition. One formulation of this prob-lem is the Approximate Gene Cluster Discovery Problem (AGCDP) which is modelled as a combinatorial optimiza-tion problem in some works. In this paper we propose an approach which produces a transformation of AGCDP into a minimum-weight star finding problem in graph. Detailed examples are also presented to further clarify the notion of the transformation. Proof of equivalence is also presented in the paper to show the equivalence of input parameters of AGCDP and the construction of the graph representing the input parameters to the problem.
html
Recommended Citation
Aborot, J. A., Adorna, H., Clemente, J. B., de Jesus, B., & Solano, G. (2012). Search for a star: Approximate gene cluster discovery problem (AGCDP) as minimization problem on graph. Retrieved from https://animorepository.dlsu.edu.ph/faculty_research/13739
Disciplines
Computer Engineering | Engineering
Keywords
Graph theory; Genomics
Upload File
wf_no
