Theoretical Lower Bound for Border Length Minimization Problem

S Srinivasan (), V Kamakoti () and A Bhattacharya ()
Additional contact information
S Srinivasan: Defence Research and Development Organization (DRDO)
V Kamakoti: Department of Computer Science and Engineering, Indian Institute of Technology (IIT)
A Bhattacharya: Defence Research and Development Organization (DRDO)

Sankhya B: The Indian Journal of Statistics, 2017, vol. 79, issue 1, No 1, 20 pages

Abstract: Abstract Biochemical analysis procedures, that include genomics and drug discovery, have been formalized to an extent that they can be automated. Large Microarrays housing DNA probes are used for this purpose. Manufacturing these microarrays involve depositing the respective DNA probes in each of its cells. The deposition is carried out iteratively by masking and unmasking cells in each step. A masked cell of the microarray that is adjacent (shares a border) to an unmasked one is at a high risk of being exposed in a deposition step. Thus, minimizing the number of such borders (Border length minimization) is crucial for reliable manufacturing of these microarrays. Given a microarray and a set of DNA probes, computing a lower bound on the border length is crucial to study the effectiveness of any algorithm that solves the border length minimization problem. A Numerical method for computing this lower bound has been proposed in the literature. This takes prohibitively large time. In practice, the DNA probes are random sequences of nucleotides. Based on this realistic assumption, this paper attempts to estimate the lower bound for the border length analytically using a probability theoretic approach by reducing the same to the problems of computing the probability distribution functions (PDF) for the Hamming Distance and the length of the longest common subsequence (LCS) between two random strings. To the best of our knowledge, no PDF is reported earlier for the length of the LCS between two random strings.

Keywords: DNA; Microarrays; Longest Common Subsequence (LCS); Border Minimization Problem (BMP); Primary 46N30; Secondary 60C05; 62P10 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13571-016-0121-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sankhb:v:79:y:2017:i:1:d:10.1007_s13571-016-0121-y

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/13571

DOI: 10.1007/s13571-016-0121-y

Access Statistics for this article

Sankhya B: The Indian Journal of Statistics is currently edited by Dipak Dey

More articles in Sankhya B: The Indian Journal of Statistics from Springer, Indian Statistical Institute
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().