Title :
Aligning ESTs to genome using multilayer unique makers
Author :
Hsu, F.R. ; Chen, J.F.
Author_Institution :
Dept. for Inf. Technol., Taichung Healthcare & Manage. Univ., Taiwan
Abstract :
As more and more genomic sequences have been sequenced and rapid growing of number of EST (expressed sequence tag), we need very fast and efficient algorithms to align ESTs to genome. ESTs contain the exon/intron structure. Let G and E denote the given genome and the given EST sequence respectively. In order to reduce the time complexity, it is quite important to locate the position of E in G efficiently. A unique maker is a sequence appeared in G only once. We can locate the position of E in G by finding unique markers contained in E. The time complexity to align ESTs to genome grows rapidly when we use longer unique markers. In this paper, we propose a multi-layer unique marker method to align ESTs to genome. Our method has the benefit of both short and long unique markers. Our algorithm can also use to locate the position of single nucleotide polymorphism (SNP). Experimental result shows that our method is much faster than common tools such as SIM4 and BLAT.
Keywords :
DNA; biology computing; genetics; multilayers; organic compounds; polymorphism; BLAT; SIM4; expressed sequence tag; genomic sequence; multilayer unique marker method; single nucleotide polymorphism; time complexity; Bioinformatics; DNA; Genomics; Humans; Information technology; Medical services; Microcomputers; Proteins; Sequences; Technology management;
Conference_Titel :
Bioinformatics Conference, 2003. CSB 2003. Proceedings of the 2003 IEEE
Print_ISBN :
0-7695-2000-6
DOI :
10.1109/CSB.2003.1227409