ABSTRACT
Use of higher order clique potentials in MRF-MAP problems has been limited primarily because of the inefficiencies of the existing algorithmic schemes. We propose a new combinatorial algorithm for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials. The algorithm runs in time O(2(k)n(3)) in the worst case (k is size of clique and n is the number of pixels). A special gadget is introduced to model flows in a higher order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem, the notions of the capacity of an edge and a cut are generalized to define a flow problem. We show that in this flow graph, when the clique potentials are submodular, the max flow is equal to the min cut, which also is the optimal solution to the problem. We show experimentally that our algorithm provides significantly better solutions in practice and is hundreds of times faster than solution schemes like Dual Decomposition [1], TRWS [2] and Reduction [3], [4], [5]. The framework represents a significant advance in handling higher order problems making optimal inference practical for medium sized cliques.
ABSTRACT
Sol-gel synthesized nickel oxide (NiO) film deposited onto indium tin oxide (ITO) coated glass plate has been utilized for the development of sensitive and stable DNA biosensor and demonstrated for diagnosis of visceral leishmaniasis also known as Kala-azar. Leishmania specific sensor is developed by immobilizing 23mer DNA sequence (oligonucleotide) identified from 18S rRNA gene sequences from Leishmania donovani. Characterization studies like X-Ray Diffraction and Scanning Electron Microscopy revealed the formation of nano-structured NiO, while immobilization of single strand (ss)-DNA of Leishmania was supported by UV-visible, Fourier Transform Infrared Spectroscopy and Scanning Electron Microscopy techniques. Response studies of ss-DNA/NiO/ITO bioelectrode are carried out using differential pulsed voltammetry in presence of methylene blue redox dye as a redox mediator. A linear response is obtained in the wide concentration range of 2 pg ml(-1) to 2 µg ml(-1) of complementary target genomic DNA (disease DNA) within the variation of 10% for 5 sets of studies. The observed results hold promise not only for diagnosis of Kala-azar patients but also hold enormous potential of the nano-NiO based probe for development of stable and sensitive biosensors.