Dispensation order generation for pyrosequencing

Carlsson, Mats and Beldiceanu, Nicolas (2004) Dispensation order generation for pyrosequencing. In: Proceedings of the Second Asia Pacific Bioinformatics Conference (APBC2004), 18-22 Jan 2004, Dunedin, New Zealand.

Full text not available from this repository.

Official URL:


This article describes a dispensation order generation algorithm for genotyping using the Pyrosequencing method. The input template of the algorithm is a slightly restricted regular expression over the DNA strings that can be expected in a given sample. The algorithm computes a dispensation order that allows for determining, for each polymorphism in the input template, the genotype of any sample. The algorithm has the structure of a non-deterministic rewrite system, which gives rise to a search tree. We show that within any branch of the search tree, the rewrite system is confluent and terminating. We use nogood generation and limited discrepancy search to prune the search tree and to focus the search for shorter dispensation orders before looking for longer ones. The algorithm as described herein assumes samples from a diploid genome, but can readily be generalized to general k-ploid genomes.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Published in Bioinformatics 2004, Volume 29; Australian Computer Science Communications, Volume 26, Number 4. Edited by Yi-Ping Phoebe Chen. ISBN-13 1-920682-11-2. ISSN 1445-1336.
ID Code:2722
Deposited On:07 Apr 2008
Last Modified:18 Nov 2009 16:13

Repository Staff Only: item control page