A Gibbs sampling approach to detection of tree motifs.
This paper introduces a method to detect tree patterns (tree motifs) in a database of rooted unordered labeled trees. The method can be viewed as an extension of the Gibbs sampling approach to detect sequence motifs. Basically, we enumerate tree topologies and for each topology we seek within the database for tree motifs with the given topology. A tree motif can be detected by matching the tree topology against the database of trees and then applying Gibbs sampling on the matching set. After completion of the process for a given tree topology, the process is restarted for the next enumerated tree topology. The method outputs for each topology the best tree motif found. We applied our method to an artificially created database of trees as well as to a database of carbohydrate (glycan) structures.
Meireles
Lidio Marx Carvalho
LM
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, 611-0011 Kyoto, Japan. lidio@kuicr.kyoto-u.ac.jp
Akutsu
Tatsuya
T
D000465:Algorithms; D001482:Base Composition; D001483:Base Sequence; D019295:Computational Biology; D003201:Computers; D016208:Databases, Factual; D008390:Markov Chains; D008433:Mathematics; D015233:Models, Statistical; D011134:Polysaccharides / Q000737:chemistry* / Q000145:classification; D011336:Probability; D012494:Sampling Studies; D017422:Sequence Analysis, DNA / Q000379:methods*
D011134:Polysaccharides