title: CLAGen: a tool for clustering and annotating gene sequences using a suffix tree algorithm.
abstract: Most multiple gene sequence alignment methods rely on conventions regarding the score of a multiple alignment in pairwise fashion. Therefore, as the number of sequences increases, the runtime of sequencing expands exponentially. In order to solve the problem, this paper presents a multiple sequence alignment method using a linear-time suffix tree algorithm to cluster similar sequences at one time without pairwise alignment. After searching for common subsequences, cross-matching common subsequences were generated, and sometimes inexact matching was found. So, a procedure aimed at masking the inexact cross-matching pairs was suggested here. In addition, BLAST was combined with a clustering tool in order to annotate the clusters generated by suffix tree clustering. The proposed method for clustering and annotating genes consists of the following steps: (1) construction of a suffix tree; (2) searching and overlapping common subsequences; (3) grouping subsequence pairs; (4) masking cross-matching pairs; (5) clustering gene sequences; (6) annotating gene clusters by the BLAST search. The performance of the proposed system, CLAGen, was successfully evaluated with 42 gene sequences in a TCA cycle (a citrate cycle) of bacteria. The system generated 11 clusters and found the longest subsequences of each cluster, which are biologically significant.
authors.affiliation: Department of Chemical Engineering, Pusan National University, Pusan 609-735, Republic of Korea. sangilh@pusan.ac.kr
authors.forename: Sang il
authors.initials: Si
authors.lastname: Han
authors.forename: Sung Gun
authors.initials: SG
authors.lastname: Lee
authors.forename: Kyung-Hoon
authors.initials: KH
authors.lastname: Kim
authors.forename: Chung Jung
authors.initials: CJ
authors.lastname: Choi
authors.forename: Young Han
authors.initials: YH
authors.lastname: Kim
authors.forename: Kyu Suk
authors.initials: KS
authors.lastname: Hwang
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D004282:Documentation / Q000379:methods; D008969:Molecular Sequence Data; D005810:Multigene Family / Q000235:genetics*; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software