The restriction mapping problem revisited

In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied techniques for restriction mapping. While double digest is NP-complete, there is no known polynomial-time algorithm for partial digest. Another disadvantage of the above techniques is that there can be multiple solutions for reconstruction. In this paper, we study a simple technique called labeled partial digest for restriction mapping. We give a fast polynomial time (O(n(2) log n) worst-case) algorithm for finding all the n sites of a DNA molecule using this technique. An important advantage of the algorithm is the unique reconstruction of the DNA molecule from the digest. The technique is also robust in handling errors in fragment lengths which arises in the laboratory. We give a robust O(n(4)) worst-case algorithm that can provably tolerate an absolute error of O(Delta/n) (where Delta is the minimum inter-site distance), while giving a unique reconstruction. We test our theoretical results by simulating the performance of the algorithm on a real DNA molecule. Motivated by the similarity to the labeled partial digest problem, we address a related problem of interest-the de novo peptide sequencing problem (ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 389-398), which arises in the reconstruction of the peptide sequence of a protein molecule. We give a simple and efficient algorithm for the problem without using dynamic programming. The algorithm runs in time O(k log k), where k is the number of ions and is an improvement over the algorithm in Chen et al. (C) 2002 Elsevier Science (USA). All rights reserved.

Mapping of local electronic properties in nanostructured CMR thin films by Scanning Tunneling Microscopy (STM) and Local Conductance Map (LCMAP)

We have investigated the local electronic properties and the spatially resolved magnetoresistance of a nanostructured film of a colossal magnetoresistive (CMR) material by local conductance mapping (LCMAP) using a variable temperature Scanning Tunneling Microscope (STM) operating in a magnetic field. The nanostructured thin films (thickness ≈500nm) of the CMR material La0.67Sr0.33MnO3 (LSMO) on quartz substrates were prepared using chemical solution deposition (CSD) process. The CSD grown films were imaged by both STM and atomic force microscopy (AFM). Due to the presence of a large number of grain boundaries (GB's), these films show low field magnetoresistance (LFMR) which increases at lower temperatures. The measurement of spatially resolved electronic properties reveal the extent of variation of the density of states (DOS) at and close to the Fermi level (EF) across the grain boundaries and its role in the electrical resistance of the GB. Measurement of the local conductance maps (LCMAP) as a function of magnetic field as well as temperature reveals that the LFMR occurs at the GB. While it was known that LFMR in CMR films originates from the GB, this is the first investigation that maps the local electronic properties at a GB in a magnetic field and traces the origin of LFMR at the GB.

Mapping of large scale 158 mu m [CII] line emission: Orion A

We present the first results of an observational programme undertaken to map the fine structure line emission of singly ionized carbon ([ CII] 157 : 7409 mum) over extended regions using a Fabry Perot spectrometer newly installed at the focal plane of a 100 cm balloon- borne far- infrared telescope. This new combination of instruments has a velocity resolution of similar to 200 km s(-1) and an angular resolution of 1.'5. During the first flight, an area of 30' x 15' in Orion A was mapped. These observations extend over a larger area than previous observations, the map is fully sampled and the spectral scanning method used enables reliable estimation of the continuum emission at frequencies adjacent to the [ CII] line. The total [ CII] line luminosity, calculated by considering up to 20% of the maximum line intensity is 0.04% of the luminosity of the far- infrared continuum. We have compared the [ CII] intensity distribution with the velocity- integrated intensity distributions of (CO)-C-13(1- 0), CI(1- 0) and CO( 3- 2) from the literature. Comparison of the [ CII], [ CI] and the radio continuum intensity distributions indicates that the largescale [ CII] emission originates mainly from the neutral gas, except at the position of M 43, where no [ CI] emission corresponding to the [ CII] emission is seen. Substantial part of the [ CII] emission from here originates from the ionized gas. The observed line intensities and ratios have been analyzed using the PDR models by Kaufman et al. ( 1999) to derive the incident UV flux and volume density at a few selected positions. The models reproduce the observations reasonably well at most positions excepting the [ CII] peak ( which coincides with the position of theta(1) Ori C). Possible reason for the failure could be the simplifying assumption of a homogeneous plane parallel slab in place of a more complicated geometry.

Contrained linear spectral unmixing technique for regional land cover mapping using MODIS data

Over the last few decades, there has been a significant land cover (LC) change across the globe due to the increasing demand of the burgeoning population and urban sprawl. In order to take account of the change, there is a need for accurate and up- to-date LC maps. Mapping and monitoring of LC in India is being carried out at national level using multi-temporal IRS AWiFS data. Multispectral data such as IKONOS, Landsat- TM/ETM+, IRS-1C/D LISS-III/IV, AWiFS and SPOT-5, etc. have adequate spatial resolution (~ 1m to 56m) for LC mapping to generate 1:50,000 maps. However, for developing countries and those with large geographical extent, seasonal LC mapping is prohibitive with data from commercial sensors of limited spatial coverage. Superspectral data from the MODIS sensor are freely available, have better temporal (8 day composites) and spectral information. MODIS pixels typically contain a mixture of various LC types (due to coarse spatial resolution of 250, 500 and 1000 m), especially in more fragmented landscapes. In this context, linear spectral unmixing would be useful for mapping patchy land covers, such as those that characterise much of the Indian subcontinent. This work evaluates the existing unmixing technique for LC mapping using MODIS data, using end- members that are extracted through Pixel Purity Index (PPI), Scatter plot and N-dimensional visualisation. The abundance maps were generated for agriculture, built up, forest, plantations, waste land/others and water bodies. The assessment of the results using ground truth and a LISS-III classified map shows 86% overall accuracy, suggesting the potential for broad-scale applicability of the technique with superspectral data for natural resource planning and inventory applications.

Landslide susceptibility mapping in the downstream region of Sharavathi river basin, Central Western Ghats

Landslides are hazards encountered during monsoon in undulating terrains of Western Ghats causing geomorphic make over of earth surface resulting in significant damages to life and property. An attempt is made in this paper to identify landslides susceptibility regions in the Sharavathi river basin downstream using frequency ratio method based on the field investigations during July- November 2007. In this regard, base layers of spatial data such as topography, land cover, geology and soil were considered. This is supplemented with the field investigations of landslides. Factors that influence landslide were extracted from the spatial database. The probabilistic model -frequency ratio is computed based on these factors. Landslide susceptibility indices were computed and grouped into five classes. Validation of LHS, showed an accuracy of 89% as 25 of the 28 regions tallied with the field condition of highly vulnerable landslide regions. The landslide susceptible map generated for the downstream would be useful for the district officials to implement appropriate mitigation measures to reduce hazards.

Image fusion in GRDSS for Land use Mapping

Image fusion techniques are useful to integrate the geometric detail of a high-resolution panchromatic (PAN) image and the spectral information of a low-resolution multispectral (MSS) image, particularly important for understanding land use dynamics at larger scale (1:25000 or lower), which is required by the decision makers to adopt holistic approaches for regional planning. Fused images can extract features from source images and provide more information than one scene of MSS image. High spectral resolution aids in identification of objects more distinctly while high spatial resolution allows locating the objects more clearly. The geoinformatics technologies with an ability to provide high-spatial-spectral-resolution data helps in inventorying, mapping, monitoring and sustainable management of natural resources. Fusion module in GRDSS, taking into consideration the limitations in spatial resolution of MSS data and spectral resolution of PAN data, provide high-spatial-spectral-resolution remote sensing images required for land use mapping on regional scale. GRDSS is a freeware GIS Graphic User Interface (GUI) developed in Tcl/Tk is based on command line arguments of GRASS (Geographic Resources Analysis Support System) with the functionalities for raster analysis, vector analysis, site analysis, image processing, modeling and graphics visualization. It has the capabilities to capture, store, process, analyse, prioritize and display spatial and temporal data.

Two-level Mapping Based Cache Index Selection for Packet Forwarding Engines

Packet forwarding is a memory-intensive application requiring multiple accesses through a trie structure. The efficiency of a cache for this application critically depends on the placement function to reduce conflict misses. Traditional placement functions use a one-level mapping that naively partitions trie-nodes into cache sets. However, as a significant percentage of trie nodes are not useful, these schemes suffer from a non-uniform distribution of useful nodes to sets. This in turn results in increased conflict misses. Newer organizations such as variable associativity caches achieve flexibility in placement at the expense of increased hit-latency. This makes them unsuitable for L1 caches.We propose a novel two-level mapping framework that retains the hit-latency of one-level mapping yet incurs fewer conflict misses. This is achieved by introducing a secondlevel mapping which reorganizes the nodes in the naive initial partitions into refined partitions with near-uniform distribution of nodes. Further as this remapping is accomplished by simply adapting the index bits to a given routing table the hit-latency is not affected. We propose three new schemes which result in up to 16% reduction in the number of misses and 13% speedup in memory access time. In comparison, an XOR-based placement scheme known to perform extremely well for general purpose architectures, can obtain up to 2% speedup in memory access time.

Hierarchical Clustering Algorithm for Land Cover Mapping Using Satellite Images

This paper presents hierarchical clustering algorithms for land cover mapping problem using multi-spectral satellite images. In unsupervised techniques, the automatic generation of number of clusters and its centers for a huge database is not exploited to their full potential. Hence, a hierarchical clustering algorithm that uses splitting and merging techniques is proposed. Initially, the splitting method is used to search for the best possible number of clusters and its centers using Mean Shift Clustering (MSC), Niche Particle Swarm Optimization (NPSO) and Glowworm Swarm Optimization (GSO). Using these clusters and its centers, the merging method is used to group the data points based on a parametric method (k-means algorithm). A performance comparison of the proposed hierarchical clustering algorithms (MSC, NPSO and GSO) is presented using two typical multi-spectral satellite images - Landsat 7 thematic mapper and QuickBird. From the results obtained, we conclude that the proposed GSO based hierarchical clustering algorithm is more accurate and robust.

Nonlinear dynamic state estimation in instrumented structures with conditionally linear Gaussian substructures

Many problems of state estimation in structural dynamics permit a partitioning of system states into nonlinear and conditionally linear substructures. This enables a part of the problem to be solved exactly, using the Kalman filter, and the remainder using Monte Carlo simulations. The present study develops an algorithm that combines sequential importance sampling based particle filtering with Kalman filtering to a fairly general form of process equations and demonstrates the application of a substructuring scheme to problems of hidden state estimation in structures with local nonlinearities, response sensitivity model updating in nonlinear systems, and characterization of residual displacements in instrumented inelastic structures. The paper also theoretically demonstrates that the sampling variance associated with the substructuring scheme used does not exceed the sampling variance corresponding to the Monte Carlo filtering without substructuring. (C) 2012 Elsevier Ltd. All rights reserved.

Quasi-based hierarchical clustering for land cover mapping using satellite images

This paper presents an improved hierarchical clustering algorithm for land cover mapping problem using quasi-random distribution. Initially, Niche Particle Swarm Optimization (NPSO) with pseudo/quasi-random distribution is used for splitting the data into number of cluster centers by satisfying Bayesian Information Criteria (BIC). Themain objective is to search and locate the best possible number of cluster and its centers. NPSO which highly depends on the initial distribution of particles in search space is not been exploited to its full potential. In this study, we have compared more uniformly distributed quasi-random with pseudo-random distribution with NPSO for splitting data set. Here to generate quasi-random distribution, Faure method has been used. Performance of previously proposed methods namely K-means, Mean Shift Clustering (MSC) and NPSO with pseudo-random is compared with the proposed approach - NPSO with quasi distribution(Faure). These algorithms are used on synthetic data set and multi-spectral satellite image (Landsat 7 thematic mapper). From the result obtained we conclude that use of quasi-random sequence with NPSO for hierarchical clustering algorithm results in a more accurate data classification.

Mapping joint ROM on a cube using electromagnetic trackers

This paper presents a unified framework using the unit cube for measurement, representation and usage of the range of motion (ROM) of body joints with multiple degrees of freedom (d.o.f) to be used for digital human models (DHM). Traditional goniometry needs skill and kn owledge; it is intrusive and has limited applicability for multi-d.o.f. joints. Measurements using motion capture systems often involve complicated mathematics which itself need validation. In this paper we use change of orientation as the measure of rotation; this definition does not require the identification of any fixed axis of rotation. A two-d.o.f. joint ROM can be represented as a Gaussian map. Spherical polygon representation of ROM, though popular, remains inaccurate, vulnerable due to singularities on parametric sphere and difficult to use for point classification. The unit cube representation overcomes these difficulties. In the work presented here, electromagnetic trackers have been effectively used for measuring the relative orientation of a body segment of interest with respect to another body segment. The orientation is then mapped on a surface gridded cube. As the body segment is moved, the grid cells visited are identified and visualized. Using the visual display as a feedback, the subject is instructed to cover as many grid cells as he can. In this way we get a connected patch of contiguous grid cells. The boundary of this patch represents the active ROM of the concerned joint. The tracker data is converted into the motion of a direction aligned with the axis of the segment and a rotation about this axis later on. The direction identifies the grid cells on the cube and rotation about the axis is represented as a range and visualized using color codes. Thus the present methodology provides a simple, intuitive and accura te determination and representation of up to 3 d.o.f. joints. Basic results are presented for the shoulder. The measurement scheme to be used for wrist and neck, and approach for estimation of the statistical distribution of ROM for a given population are also discussed.

Mapping the apoptosis inducing domain of an immunomodulatory protein: glycodelin A

Glycodelin A (GdA) is a dimeric glycoprotein synthesized by the human endometrium under progesterone regulation. Based on the high sequence similarity with beta-lactoglobulin, it is placed under the lipocalin superfamily. The protein is one of the local immunomodulators present at the feto-maternal interface which affects both the innate as well as the acquired arms of the immune system, thereby bringing about successful establishment and progression of pregnancy. Our previous studies revealed that the domain responsible for the immunosuppressive activity of glycodelin lies on its protein backbone and the glycans modulate the same. This study attempts to further delineate the apoptosis inducing region of GdA. Our results demonstrate that the stretch of amino acid sequence between Met24 to Leu105 is necessary and sufficient to inhibit proliferation of T cells and induce apoptosis in them. Further, within this region the key residues involved in harboring the activity were shown to be present between Asp52 and Ser65.