Title: Optimal group testing algorithms with interval queries and their application to splice site detection

Authors: Ferdinando Cicalese, Peter Damaschke, Ugo Vaccaro

Addresses: Institute of Bioinformatics, Center of Biotechnology (CeBiTec), Bielefeld University, 33594 Bielefeld, Germany. ' School of Computer Science and Engineering, Chalmers University, 41296 Goteborg, Sweden. ' Department of Computer Science and Applications, University of Salerno, 84081 Baronissi (SA), Italy

Abstract: Given an ordered set of n items and an unknown subset P of up to p positive elements, we want to identify P by asking the least number of queries |does Q intersect P?| where Q must consist of consecutive elements. This Interval Group Testing problem arises in the context of splice site detection in genes. We study algorithms that operate in a few stages where queries chosen depending on previous answers, are performed in parallel. We obtain tight bounds for two-stage strategies. Finally, we get results for any number of stages and positives.

Keywords: splice sites; exon-intron boundaries; gene prediction; combinatorial search; group testing; interval queries; bioinformatics; splice site detection; genes.

DOI: 10.1504/IJBRA.2005.008441

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.4, pp.363 - 388

Published online: 20 Dec 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article