Analysis of ribosomal RNA sequences by combinatorial clustering.
We present an analysis of multi-aligned eukaryotic and procaryotic small subunit rRNA sequences using a novel segmentation and clustering procedure capable of extracting subsets of sequences that share common sequence features. This procedure consists of: i) segmentation of aligned sequences using a dynamic programming procedure, and subsequent identification of likely conserved segments; ii) for each putative conserved segment, extraction of a locall homogeneous cluster using a novel polynomial procedure; and iii) intersection of clusters associated with each conserved segment. Aside from their utilit in processing large gap-filled multi-alignments, these algorithms can be applied to a broad spectrum of rRNA analysis functions such as subalignment, phylogenetic subtree extraction and construction, and organism tree-placement, and can serve as a framework to organize sequence data in an efficient and easily searchable manner. The sequence classification we obtained using the method presented here shows a remarkable consistency with the independently constructed eukaryotic phylogenetic tree.
Xing
P
P
DIMACS and CS Department, Rutgers University, Piscataway, NJ 08855-1179, USA. xingpoe@cs.rutgers.edu
Kulikowski
C
C
Muchnik
I
I
Dubchak
I
I
Wolf
D M
DM
Spengler
S
S
Zorn
M
M
D000465:Algorithms; D000818:Animals; D016000:Cluster Analysis; D020650:Combinatorial Chemistry Techniques; D056890:Eukaryota / Q000235:genetics; D005800:Genes, Fungal; D017125:Genes, Protozoan; D015233:Models, Statistical; D010802:Phylogeny; D012335:RNA, Ribosomal / Q000235:genetics*; D012337:RNA, Ribosomal, 18S / Q000235:genetics; D017423:Sequence Analysis, RNA / Q000379:methods*
D012335:RNA, Ribosomal; D012337:RNA, Ribosomal, 18S