Ni, BingBingNiWong, Man-HonMan-HonWongLam, Chi-Fai DavidChi-Fai DavidLamProf. LEUNG Kwong Sak2023-03-162023-03-162014International Journal of Data Mining and Bioinformatics, 2014, Vol. 9 (4), pp 358-3851748-56731748-5681http://hdl.handle.net/20.500.11861/7500This paper addresses the approximate matching problem in a database consisting of multiple DNA sequences, where the proposed approach applies Agrep to a new truncated suffix array, r-NSA. The construction time of the structure is linear to the database size, and the computations of indexing a substring in the structure are constant. The number of characters processed in applying Agrep is analysed theoretically, and the theoretical upper-bound can approximate closely the empirical number of characters, which is obtained through enumerating the characters in the actual structure built. Experiments are carried out using (synthetic) random DNA sequences, as well as (real) genome sequences including Hepatitis-B Virus and X-chromosome. Experimental results show that, compared to the straight-forward approach that applies Agrep to multiple sequences individually, the proposed approach solves the matching problem in much shorter time. The speed-up of our approach depends on the sequence patterns, and for highly similar homologous genome sequences, which are the common cases in real-life genomes, it can be up to several orders of magnitude.enNumerical Suffix ArrayTruncated Suffix ArrayAgrepMultiple Sequences Approximate MatchingPeer Reviewed Journal Article10.1504/IJDMB.2014.062145