NDLI: Discovering local structure in gene expression data: the order-preserving submatrix problem

Please wait, while we are loading the content...

Computational structural proteomics and virtual ligand screening

Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures

Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion

Monotony of surprise and large-scale quest for unusual words

DNA sequence evolution with neighbor-dependent mutation

A new approach to analyzing gene expression time series data

Discovering local structure in gene expression data: the order-preserving submatrix problem

The restriction scaffold problem

Comparison of minisatellites

Trilogy: discovery of sequence-structure patterns across diverse proteins

Microarray analysis of vertebrate embryonic neural induction

Provably sensitive Indexing strategies for biosequence similarity search

Structural alignment of large—size proteins via lagrangian relaxation

Designing RNA structures: natural and artificial selection

Inferring domain-domain interactions from protein-protein interactions

Analysis of gene expression profiles: class discovery and leaf ordering

A bayesian approach to transcript estimation from gene array data: the BEAM technique

Tests for gene clustering

Recent duplication, evolution and assembly of the human genome

Approximate matching of secondary structures

Applied computational genomics: polymorphism prediction, data mining and genomic analysis

Haplotyping as perfect phylogeny: conceptual framework and efficient solutions

Handling long targets and errors in sequencing by hybridization

Sequencing by hybridization using direct and reverse cooperating spectra

Lymphocyte turnover in HIV-1 infection and the role of the thymus in SIV infection

Finding motifs in the twilight zone

Phase-independent rhythmic analysis of genome-wide expression patterns

Significance Of inter-species matches when evolutionary rate varies

Combining pairwise sequence similarity and support vector machines for remote protein homology detection

Revealing protein structures: a new method for mapping antibody epitopes

Set association analysis of SNP case-control and microarray data

Picking alignments from (steiner) trees

String barcoding: uncovering optimal virus signatures

Biological and computational annotation of the Drosophila Genome Sequence

From promoter sequence to expression: a probabilistic framework

Probabilistic hierarchical clustering for biological data

An algorithm to enumerate all sorting reversals

Discriminative motifs

A dimensionality reduction approach to modeling protein flexibility

Sequencing the human genome

Toward a proteome atlas for C. Elegans

Deconvolving sequence variation in mixed DNA populations

Microarrays: how many do you need?

Discovering local structure in gene expression data: the order-preserving submatrix problem

Content Provider	ACM Digital Library
Author	Karp, Richard Yakhini, Zohar Ben-Dor, Amir Chor, Benny
Abstract	This paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. Most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. Our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset G of the genes and a subset T of the experiments. Specifically, we look for order-preserving submatrices (OPSMs), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the OPSM search problem is NP-hard in the worst case). Such a pattern might arise, for example, if the experiments in T represent distinct stages in the progress of a disease or in a cellular process, and the expression levels of all genes in G vary across the stages in the same way.We define a probabilistic model in which an OPSM is hidden within an otherwise random matrix. Guided by this model we develop an efficient algorithm for finding the hidden OPSM in the random matrix. In data generated according to the model the algorithm recovers the hidden OPSM with very high success rate. Application of the methods to breast cancer data seems to reveal significant local patterns.Our algorithm can be used to discover more than one OPSM within the same data set, even when these OPSMs overlap. It can also be adapted to handle relaxations and extensions of the OPSM condition. For example, we may allow the different rows of G x T to induce similar but not identical orderings of the columns, or we may allow the set T to include more than one representative of each stage of a biological process.
Starting Page	49
Ending Page	57
Page Count	9
File Format	PDF
ISBN	1581134983
DOI	10.1145/565196.565203
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-04-18
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in