title: Identification of regulatory binding sites using minimum spanning trees.
abstract: Recognition of protein-binding sites from the upstream regions of genes is a highly important and unsolved problem. In this paper, we present a new approach for studying this challenging issue. We formulate the binding-site recognition problem as a cluster identification problem, i.e., to identify clusters in a data set that exhibit significantly different features (e.g., density) than the overall background of the data set. We have developed a general framework for solving such a cluster identification problem. The foundation of the framework is a rigorous relationship between data clusters and subtrees of a minimum spanning tree (MST) representation of a data set. We have proposed a formal and general definition of clusters, and have demonstrated that a cluster is always represented as a connected component of the MST, and further it corresponds to a substring of a linear representation of the MST. Hence a cluster identification problem is reduced to a problem of finding substrings with certain features, for which algorithms have been developed. We have applied this MST-based cluster identification algorithm to a number of binding site identification problems. The results are highly encouraging.
authors.affiliation: Protein Informatics Group, Life Sciences Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831-6480, USA.
authors.forename: Victor
authors.initials: V
authors.lastname: Olman
authors.forename: Dong
authors.initials: D
authors.lastname: Xu
authors.forename: Ying
authors.initials: Y
authors.lastname: Xu
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D001665:Binding Sites / Q000235:genetics; D016000:Cluster Analysis; D019295:Computational Biology; D004269:DNA, Bacterial / Q000235:genetics / Q000378:metabolism; D004271:DNA, Fungal / Q000235:genetics / Q000378:metabolism; D030562:Databases, Protein; D029968:Escherichia coli Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D006801:Humans; D011485:Protein Binding; D011506:Proteins / Q000737:chemistry* / Q000235:genetics* / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D013597:Systems Analysis
chemical_list: D004269:DNA, Bacterial; D004271:DNA, Fungal; D029968:Escherichia coli Proteins; D011506:Proteins; D029701:Saccharomyces cerevisiae Proteins