title: Analysis of ribosomal RNA sequences by combinatorial clustering.
abstract: 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.
authors.affiliation: DIMACS and CS Department, Rutgers University, Piscataway, NJ 08855-1179, USA. xingpoe@cs.rutgers.edu
authors.forename: P
authors.initials: P
authors.lastname: Xing
authors.forename: C
authors.initials: C
authors.lastname: Kulikowski
authors.forename: I
authors.initials: I
authors.lastname: Muchnik
authors.forename: I
authors.initials: I
authors.lastname: Dubchak
authors.forename: D M
authors.initials: DM
authors.lastname: Wolf
authors.forename: S
authors.initials: S
authors.lastname: Spengler
authors.forename: M
authors.initials: M
authors.lastname: Zorn
mesh_terms: 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*
chemical_list: D012335:RNA, Ribosomal; D012337:RNA, Ribosomal, 18S