Efficient non-unique probes selection algorithms for DNA microarray

Ping Deng; Thai, My T.; Qingkai Ma; Weili Wu
January 2008
BMC Genomics;2008 Supplement 1, Vol. 9, Special section p1
Academic Journal
Background: Temperature and salt concentration are very helpful experimental conditions for a probe to hybridize uniquely to its intended target. In large families of closely related target sequences, the high degree of similarity makes it impossible to find a unique probe for every target. We studied how to select a minimum set of non-unique probes to identify the presence of at most d targets in a sample where each non-unique probe can hybridize to a set of targets. Results: We proposed efficient algorithms based on Integer Linear Programming to select a minimum number of non-unique probes using d-disjunct matrices. Our non-unique probes selection can also identify up to d targets in a sample with at most k experimental errors. The decoding complexity of our algorithms is as simple as O(n). The experimental results show that the decoding time is much faster than that of the methods using d-separable matrices while running time and solution size are comparable. Conclusions: Since finding unique probes is often not easy, we make use of non-unique probes. Minimizing the number of non-unique probes will result in a smaller DNA microarry design which leads to a smaller chip and considerable reduction of cost. While minimizing the probe set, the decoding ability should not be diminished. Our non-unique probes selection algorithms can identify up to d targets with error tolerance and the decoding complexity is O(n).


Related Articles

  • Using a Genetic Algorithm and a Perceptron for Feature Selection and Supervised Class Learning in DNA Microarray Data. Michal Karzynski; Álvaro Mateos; Javier Herrero; Joaquín Dopazo // Artificial Intelligence Review;Oct2003, Vol. 20 Issue 1/2, p39 

    Class prediction and feature selection is key in the context of diagnostic applications of DNA microarrays. Microarray data is noisy and typically composed of a low number of samples and a large number of genes. Perceptrons can constitute an efficient tool for accurate classification of...

  • Prediction of Compound Signature Using High Density Gene Expression Profiling. Hamadeh, Hisham K.; Bushel, Pierre R.; Jayadev, Supriya; DiSorbo, Olimpia; Bennett, Lee; Leping Li; Tennant, Raymond; Stoll, Raymond; Barrett, J. Carl; Paules, Richard S.; Blanchard, Kerry; Afshari, Cynthia A. // Toxicological Sciences;Jun2002, Vol. 67 Issue 2, p232 

    DNA microarrays, used to measure the gene expression of thousands of genes simultaneously, hold promise for future application in efficient screening of therapeutic drugs. This will be aided by the development and population of a database with gene expression profiles corresponding to biological...

  • Improving prediction accuracy of tumor classification by reusing genes discarded during gene selection. Yang, Jack Y.; Guo-Zheng Li; Hao-Hua Meng; Qu Yang, Mary; Youping Deng // BMC Genomics;2008 Supplement 1, Vol. 9, Special section p1 

    Background: Since the high dimensionality of gene expression microarray data sets degrades the generalization performance of classifiers, feature selection, which selects relevant features and discards irrelevant and redundant features, has been widely used in the bioinformatics field. Multitask...

  • Selecting subsets of newly extracted features from PCA and PLS in microarray data analysis. Guo-Zheng Li; Hua-Long Bu; Qu Yang, Mary; Xue-Qiang Zeng; Yang, Jack Y. // BMC Genomics;2008 Supplement 2, Vol. 9, Special section p1 

    Background: Dimension reduction is a critical issue in the analysis of microarray data, because the high dimensionality of gene expression microarray data set hurts generalization performance of classifiers. It consists of two types of methods, i.e. feature selection and feature extraction....

  • Advances in metaheuristics for gene selection and classification of microarray data. Duval, Béatrice; Jin-Kao Hao // Briefings in Bioinformatics;Jan2010, Vol. 11 Issue 1, p127 

    Gene selection aims at identifying a (small) subset of informative genes from the initial data in order to obtain high predictive accuracy for classification. Gene selection can be considered as a combinatorial search problem and thus be conveniently handled with optimization methods. In this...

  • ParaSAM: a parallelized version of the significance analysis of microarrays algorithm. Sharma, Ashok; Jieping Zhao; Podolsky, Robert; McIndoe, Richard A. // Bioinformatics;Jun2010, Vol. 26 Issue 11, p1465 

    Motivation: Significance analysis of microarrays (SAM) is a widely used permutation-based approach to identifying differentially expressed genes in microarray datasets. While SAM is freely available as an Excel plug-in and as an R-package, analyses are often limited for large datasets due to...

  • A Hybrid Approach for Selection of Relevant Features for Microarray Datasets. Agrawal, R. K.; Bala, Rajni // Proceedings of World Academy of Science: Engineering & Technolog;2007, Vol. 23, p281 

    Developing an accurate classifier for high dimensional microarray datasets is a challenging task due to availability of small sample size. Therefore, it is important to determine a set of relevant genes that classify the data well. Traditionally, gene selection method often selects the top...

  • MINING OF IMPORTANT INFORMATIVE GENES AND CLASSIFIER CONSTRUCTION FOR CANCER DATASET. Pati, Soumen Kumar; Das, Asit Kumar // International Journal on Soft Computing;Aug2012, Vol. 3 Issue 3, p69 

    Microarray is a useful technique for measuring expression data of thousands or more of genes simultaneously. One of challenges in classification of cancer using high-dimensional gene expression data is to select a minimal number of relevant genes which can maximize classification accuracy....

  • AN EFFICIENT MINING PROCEDURE FOR GENE SELECTION BY USING SELECT ATTRIBUTES. ANUSUYA, S.; KARTHIKEYAN, R. // International Journal of Research in Computer Application & Mana;Apr2013, Vol. 3 Issue 4, p104 

    We propose a novel gene selection algorithm based on select attributes. The proposed algorithm eliminates gene redundancy automatically and yields a very small number of cancer related genes. Using the selected genes on the cancer classification, the robust classification accuracy has been...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics