CLAGen: a tool for clustering and annotating gene sequences using a suffix tree algorithm.
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.
Han
Sang il
Si
Department of Chemical Engineering, Pusan National University, Pusan 609-735, Republic of Korea. sangilh@pusan.ac.kr
Lee
Sung Gun
SG
Kim
Kyung-Hoon
KH
Choi
Chung Jung
CJ
Kim
Young Han
YH
Hwang
Kyu Suk
KS
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