title: Automatic discovery of sub-molecular sequence domains in multi-aligned sequences: a dynamic programming algorithm for multiple alignment segmentation.
abstract: Automatic identification of sub-structures in multi-aligned sequences is of great importance for effective and objective structural/functional domain annotation, phylogenetic treeing and other molecular analyses. We present a segmentation algorithm that optimally partitions a given multi-alignment into a set of potentially biologically significant blocks, or segments. This algorithm applies dynamic programming and progressive optimization to the statistical profile of a multi-alignment in order to optimally demarcate relatively homogenous sub-regions. Using this algorithm, a large multi-alignment of eukaryotic 16S rRNA was analyzed. Three types of sequence patterns were identified automatically and efficiently: shared conserved domain; shared variable motif; and rare signature sequence. Results were consistent with the patterns identified through independent phylogenetic and structural approaches. This algorithm facilitates the automation of sequence-based molecular structural and evolutionary analyses through statistical modeling and high performance computation.
authors.affiliation: Center for Bioinformatics and Computational Genomics, NERSC, Berkeley, CA 94720, USA.
authors.forename: E P
authors.initials: EP
authors.lastname: Xing
authors.forename: D M
authors.initials: DM
authors.lastname: Wolf
authors.forename: I
authors.initials: I
authors.lastname: Dubchak
authors.forename: S
authors.initials: S
authors.lastname: Spengler
authors.forename: M
authors.initials: M
authors.lastname: Zorn
authors.forename: I
authors.initials: I
authors.lastname: Muchnik
authors.forename: C
authors.initials: C
authors.lastname: Kulikowski
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D017124:Conserved Sequence; D008957:Models, Genetic; D012336:RNA, Ribosomal, 16S; D016415:Sequence Alignment
chemical_list: D012336:RNA, Ribosomal, 16S