Efficient combinatorial algorithms for DNA microarray design

The advent of efficient genome sequencing tools and high-throughput experimentalbiotechnology has led to enonnous progress in the life science. DNA microarrayis among the most important innovations. It allows to measure the expression forthousands of genes simultaneously by analysing the hybridisation data. Such measurementshave been proved to be invaluable in understanding the development ofdiseases such as cancer. However, the analysis of data is non-trivial since the hybridisationdata relies on the quality of DNA microarray. High quality DNA microarraywill lead to more efficient hybridisation and stronger signal.and reliability.The reliability of data is essential. Thus, the development of novel algorithms andtechniques for DNA microarray design is crucial.This thesis considers a number of combinatorial issues in selecting, placing,and synthesising probes during the DNA microarray design process. A probe isa specific sequence of single-stranded DNA or RNA, typically labelled with a radioactiveor fluorescent tag, which is designed to bind to, and thereby identify, aparticular segment of DNA (or RNA). The probe selection problem we studied isto find for each gene sequence a unique probe such that every gene in the givendataset can be identified. However, due to homology, sometimes a gene does nothave a unique probe, then we use a small number of non-unique probes to identifya gene. The challenge of the problem is that there are many candidate probes ina gene sequence and we have to find the right one (or a small subset) efficiently.A randomised probe selection algorithm for DNA microarray design is proposed.The algorithm overcomes some existing algorithms demanding optimal probes by exhaustive search. \Ve implement the randomised probe selection algorithm anddevelop a probe selection software RANDPS. Investigations using several real-lifemicroarray datasets show that algorithm is able to find high quality probes.Nevertheless, the number of the probes selected might be too large for placingin a single microarray, thus minimising the number of probes is an important objective,since it is proportional to the cost of the microarray experiment. Therefore,we investigate the string barcoding problem in which a set of non-unique probes isgiven and the probes have to be chosen from the given set of probes. The objective isto use an appropriate combination of probes with minimum cardinality such that allgenes in the dataset can be distinguished. An almost optimal O(nlSllog3 n)-timeapproximation algorithm for the considered problem is presented. The approximationprocedure is a modification of the algorithm due to Berman et a1. [l0] whichobtains the best possible approximation ratio (1 + In n). The improved time complexityis a direct consequence of more careful management of processed sets, useof several specialised graph and string data structures, as well as tighter time complexityanalysis based on an amortised argument.After probes are selected, they are then synthesised on the microarrays by usinga light-directed chemical process in which unintended illumination may contaminatethe quality of the microarray experiments. Border length is a measure of theamount of unwanted illumination and the objective of this problem is to minimisethe total border length during probe synthesis process. This problem is believed tobe NP-hard and approximation of the BMP problem in asynchronous synthesis isstudied. As far as we know, this is the first result with proved performance guarantee.The main result is an O(vnlog2 n)-approximation, where n is the number ofprobes to be synthesised. In the case where the placement is given in advance, weshow that the problem is O(10g2 n)-approximable. A related problem called agreementmaximisation problem (MAP) is also considered in this chapter. In contrast toBMp, we show that MAP admits a constant approximation even when placement isnot given in advance.Supplied by The British Library - 'The world's knowledge'