CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Optimal group testing strategies with interval queries and their application to splice site detection

Ferdinando Cicalese ; Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Ugo Vaccaro
International Workshop on Bioinformatics Research and Applications IWBRA 2005 (part of ICCS 2005), Lecture Notes in Computer Science (0302-9743). Vol. 3515 (2005), p. 1029-1037.
[Konferensbidrag, refereegranskat]

The classical Group Testing Problem is: Given a finite set of items {1,2,..., n} and an unknown subset P of up to p positive elements, identify P by asking the least number of queries of the type ``does the subset Q intersect P?". In our case, Q must be a subset of consecutive elements. This problem naturally arises in several scenarios, most notably in Computational Biology. We focus on algorithms in which queries are arranged in stages: in each stage, queries can be performed in parallel, and be chosen depending on the answers to queries in previous stages. Algorithms that operate in few stages are usually preferred in practice. First we study the case p=1 comprehensively. For two-stage strategies for arbitrary p we obtain asymptotically tight bounds on the number of queries. Furthermore we prove bounds for any number of stages and positives, and we discuss the problem with the restriction that query intervals have some bounded length d.

Nyckelord: splice sites, combinatorial group testing, gene prediction

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 5101