Automatic discovery of sub-molecular sequence domains in multi-aligned sequences: a dynamic programming algorithm for multiple alignment segmentation.
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.
Xing
E P
EP
Center for Bioinformatics and Computational Genomics, NERSC, Berkeley, CA 94720, USA.
Wolf
D M
DM
Dubchak
I
I
Spengler
S
S
Zorn
M
M
Muchnik
I
I
Kulikowski
C
C
D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D017124:Conserved Sequence; D008957:Models, Genetic; D012336:RNA, Ribosomal, 16S; D016415:Sequence Alignment
D012336:RNA, Ribosomal, 16S