Non-Unique oligonucleotide probe selection heuristics

The non-unique probe selection problem consists of selecting both unique and nonunique oligonucleotide probes for oligonucleotide microarrays, which are widely used tools to identify viruses or bacteria in biological samples. The non-unique probes, designed to hybridize to at least one target, are used as alternatives when the design of unique probes is particularly difficult for the closely related target genes. The goal of the non-unique probe selection problem is to determine a smallest set of probes able to identify all targets present in a biological sample. This problem is known to be NP-hard. In this thesis, several novel heuristics are presented based on greedy strategy, genetic algorithms and evolutionary strategy respectively for the minimization problem arisen from the non-unique probe selection using the best-known ILP formulation. Experiment results show that our methods are capable of reducing the number of probes required over the state-of-the-art methods.

Name thesis:degree_name

M.Sc.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Windsor

Year dc:date.issued

2008

Author dc:creator

• Wang, Lili

Advisor dc:contributor.advisor

• Ngom, Alioune

Contributors dc:contributor

• mita@uwindsor.ca

Licence

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en_CA

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14776/8890

OAI identifier oai:identifier

oai:uwindsor.scholaris.ca:20.500.14776/8890