Department of Computer Science
 Rutgers University

Home page

Home page  Contact us  Site map 

 

 

 

MCPD: Markov Chain Pooling Decoder

What is MCPD?

In Molecular Biology, for example for creating physical maps, one faces the problem that a large number of clones from a clone library has to be screened (tested) for a particular site. Pooling is a strategy for cutting down the number of tests by testing pools (i.e., groups) of clones. Decoding infers from the results of the pool assays the probability that a particular clone is positive.

What is it good for?

In the human chromosome 16 mapping effort at Los Alamos National Laboratory this approach (and software) was used successfully to reduce the number of tests from about 1300 to about 60 per probe. The savings get even more dramatic for libraries with larger number of clones.

MCPD was used for a library with 442,368 clones. This library is divided up into 8 parts, each of which gets pooled into 94 pools (55,296 clones, 94 pools, each clone is in 8 pools, each pool contains about 4,600 clones). Instead of 55,296 individual screenings we only require about 100 (94 screenings for the pools plus confirmatory tests).

What does Markov have to do with it ?

To make the computations feasible, one has to resort to a Markov Chain Monte Carlo Method for the computation of marginal probabilities of individual clones being positive.

Copyright

Copyright, 1994-1999, The Regents of the University of California. This software was produced under U.S. Government contract(DOE W-7405-ENG-35) by Los Alamos National Laboratory, which is operated by the University of California for the U.S. Department of Energy. The U.S Government is licensed to use, reproduce, and distribute this software. Permission is granted to the public to copy and use this software without charge, provided that this Notice and any statement of authorship are reproduced on all copies. Neither the Government nor the University makes any warranty, express or implied, or assumes any liability or responsibility for the use

Distribution & Installation

Download version 2.02 as a gzip tar archive. After Downloading gunzip und untar it, change into the MCDP-2.02 directory and type make. Done.

Plattforms

MCPD was compiled with gcc (2.7.x versions up to 3.2.x) and the vendor-supplied compilers on various versions of SunOS, Solaris, AIX, Tru64 and Linux. Since the software does not use any non-standard packages I do expect it to compile and run flawlessly on other plattforms.

Documentation

You can take a look at the Readme file and a somewhat more elaborate manual. To understand what MCPD is doing in detail refer to the publication below.

Publications

Knill, E. and Schliep, A. and Torney, D. C.. Interpretation of pooling experiments using the Markov chain Monte Carlo method (1996) [details]

Schliep, Alexander and Rahmann, Sven. Decoding non-unique oligonucleotide hybridization experiments of targets related by a phylogenetic tree (2006) [details]

Schliep, Alexander and Torney, David C. and Rahmann, Sven. Group testing with DNA chips: generating designs and decoding experiments (2003) [details]