Identification of regulatory binding sites using minimum spanning trees.
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.
Olman
Victor
V
Protein Informatics Group, Life Sciences Division, Oak Ridge National Laboratory, Oak Ridge, TN 37831-6480, USA.
Xu
Dong
D
Xu
Ying
Y
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
D004269:DNA, Bacterial; D004271:DNA, Fungal; D029968:Escherichia coli Proteins; D011506:Proteins; D029701:Saccharomyces cerevisiae Proteins