QualityBased Similarity Search for Biological Sequence Databases Xuehui Li.pdfVIP

Quality-Based Similarity Search for Biological Sequence Databases Xuehui Li Tamer Kahveci CISE Department,University of Florida,Gainesville,FL 32611 {xli, tamer}@cise.ufl.edu Position #: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Abstract Sequence 1: G A A T A A T A A T A A T A W S V W S P T V L L S Low-Complexity Regions (LCRs) of biological sequences Position #: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 are the main source of false positives in similarity searches Sequence 2: P P Q K M K A A T A A T A A T A A T R D for biological sequence databases. We consider the prob- Figure 1: Two sequences that have the same LCR indicated by lem of finding similar sequences when the locations of the LCRs are not known precisely. We develop a formulation the underlined letters. Here, the LCRs are composed of a repeating to measure the quality of each letter in a sequence. The pattern of AAT. quality value of a letter is the probability for that letter to be in a non-LCR. We show that the quality values can Traditional sequence similarity search methods pro- be employed in two fundamental approaches to the se- duce many false positives due to LCRs in biological se- quence search problem to reduce the number of false pos- quences. We use BLAST [1], one of the popular simi- itives produced