David E. Culler, Richard M. Karp, Eunice E. Santos, Klaus Erik, Thorsten Von Eicken
serve as a basis for the design and analysis of fast, portable parallel algorithms, such as algorithms that can be implemented effectively on a wide variety of current and future parallel machines....
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to the yeast S. cerevisiae and the bacteria H. pylori. Our...
Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir, Richard M. Karp
Population stratification can be a serious obstacle in the analysis of genomewide association studies. We propose a method for evaluating the significance of association scores in whole-genome...
Torque: topology-free querying of protein interaction networks (2009)
Bruckner, Sharon, Hüffner, Falk, Karp, Richard M., Shamir, Ron, Sharan, Roded
Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in...
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to the yeast S. cerevisiae and the bacteria H. pylori. Our...
Richard M. Karp, Scott Shenker, Christos H. Papadimitriou
We present a simple, exact algorithm for identifying in a multiset the items with frequency more than a threshold θ. The algorithm requires two passes, linear time, and space 1/θ. The first pass is...
Samantha Riesenfeld, Advisor Prof, Richard M. Karp, Satish Rao, Alistair Sinclair, Dorit Hochbaum
Combinatorial optimization, algorithms, and algorithmic tools for computational biology. Also, machine learning, applied probability, metric embeddings, and networks.
Amoolya H Singh, Richard M Karp, Mentor Dr. Peer Bork, Mentor Dr. Desmond Mascarenhas, Mentors Drs, ...
Research Interests: mathematical modeling and simulation of biological systems; dynamics and evolution of gene regulatory networks; comparative (meta)genomics; bacterial stress response and...
Error-Resilient DNA Computation (Preliminary Version) (2008)
Richard M. Karp, Claire Kenyont, Orli Waartss
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primi-tives, Extract-A-Bit, which splits a test tube into two test tubes according to the...
Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny (2008)
Eran Halperiny, Richard M. Karp
Abstract Each person's genome contains two copies of each chromosome, one inherited from the father and the other from the mother. A person's genotype specifies the pair of bases at each...
Abstract Algorithms for Choosing Di erential Gene Expression Experiments (2007)
Richard M. Karp, Roland Stoughton, Ka Yee Yeung
Understanding biological systems at the level of genes and proteins is a major challenge. In this paper we represent the interactions among external environmental inputs and genes in a biological...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (2007)
Richard Karp Itsik, Richard M. Karp, Ron Shamir
Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using uorescence microscopy. The real-life problem...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (2007)
Richard M. Karp, Itsik Pe'er, Ron Shamir
Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using uorescence microscopy. The real-life problem...
Roded Sharan, Trey Ideker, Brian Kelley, Ron Shamir, Richard M. Karp
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to nd complexes that are common to the yeast S. cerevisiae and the bacteria H. pylori. Our...
The restriction scaffold problem (2007)
Amir Ben-dor, Richard M. Karp, Benno Schwikowski, Ron Shamir
Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation and relative distance is unknown. We propose...
R. J. Flynn, H. Hadimioglu, A In, Third Conference Hypercube, Concurten Compulers, Robert J. Fowler, ...
correction techniques for large disk arrays. In Third International Conference on Architectural Suppot!
Garth A. Gibson, Lisa Hellerstein, Richard M. Karp, Y H. Katz
busy almost all the time. We have observed this same phenomenon in other tools, such as those devised for file compression and image transposition. We have been unable to find a practical application...
We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the...
Daniel P. Fasulo, Tao Jiang, Richard M. Karp, Reuben Settergren, Edward C. Thayer
Multiple Complete Digest (MCD) mapping is a method of determining the locations of restriction sites along a target DNA strand. The resulting restriction map has many potential applications in DNA...
Competitive Paging Algorithms Amos Fiat 1 (2007)
Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
Nearly Optimal Competitive Online Replacement (2007)
This paper studies the following online replacement problem. There is a real function f(t), called the flow rate, defined over a finite time horizon [0; T ]. It is known that m f(t) M for some reals...
Sorting and Selection in Posets (2007)
Daskalakis, Constantinos, Karp, Richard M., Mossel, Elchanan, Riesenfeld, Samantha, Verbin, Elad
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs of objects are...
Probabilistic Analysis of Linear Programming Decoding (2007)
Daskalakis, Constantinos, Dimakis, Alexandros G., Karp, Richard M., Wainwright, Martin J.
We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming...
Comparing Protein Interaction Networks via a Graph Match-and-Split Algorithm (2007)
Narayanan, Manikandan, Karp, Richard M.
We present a method that compares the protein interaction networks of two species to detect functionally similar (conserved) protein modules between them. The method is based on an algorithm we...
Sorting and Selection in Posets (2007)
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study a more general setting, in which some pairs of objects are...
Linked Decompositions of Networks and the Power of Choice in Polya Urns (2007)
Henry Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou
A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about...
On the Price of Heterogeneity in Parallel Systems (2007)
P. Brighten Godfrey, Richard M. Karp
Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the...
I.: Balancing traffic load in wireless networks with curveball routing (2007)
Lucian Popa, Afshin Rostamizadeh, Richard M. Karp, Christos Papadimitriou
We address the problem of balancing the traffic load in multi-hop wireless networks. We consider a point-to-point communicating network with a uniform distribution of source-sink pairs. When routing...
A probabilistic model for the survivability of cells (2005)
Adler, Ilan, Ahn, Hyun-Soo, Karp, Richard M., Ross, Sheldon M.
Consider n cells, of which some are target cells, and suppose that each cell has a weight. The cells are killed in a sequential manner, with each currently live cell being the next one killed with a...
A Linear Algorithm for Testing Equivalence of Finite Automata. (2005)
Hopcroft,John E., Karp,Richard M.
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of...
Efficient algorithms for detecting signaling pathways in protein interaction networks (2005)
Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan
Abstract. The interpretation of large-scale protein network data depends on our ability to identify significant sub-structures in the data, a computationally intensive task. Here we adapt and extend...
Efficient algorithms for detecting signaling pathways in protein interaction networks (2005)
Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan
The interpretation of large-scale protein network data depends on our ability to identify significant substructures in the data, a computationally intensive task. Here we adapt and extend efficient...
Efficient algorithms for detecting signaling pathways in protein interaction networks (2005)
Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan
Abstract. The interpretation of large-scale protein network data depends on our ability to identify significant sub-structures in the data, a computationally intensive task. Here we adapt and extend...
MATHEMATICAL MODELS OF INFORMATION SYSTEMS (2004)
Arnold, Richard F., Garner, Harvey L., Karp, Richard M., Lawler, Eugene L.
The primary objective of this effort is the study and development of mathematical models of information processing systems. The general area of research includes machine design, automata theory, and...
Roded Sharan, Trey Ideker, Brian Kelley, Ron Shamir, Richard M. Karp
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to yeast S. Cerevisiae and bacteria H. pylori. Our analysis...
Reconstructing chain functions in genetic networks (2004)
Irit Gat-viks, Richard M. Karp, Ron Shamir, Roded Sharan
Abstract. The following problems arise in the analysis of biological networks: We have a boolean function of n variables, each of which has some default value. An experiment fixes the values of any...
Perfect phylogeny and haplotype assignment (2004)
Eran Halperin, Richard M. Karp
This paper is concerned with the reconstruction of perfect phylogenies from binary character data with missing values, and related problems of inferring complete haplotypes from haplotypes or...
LOGOS: A Modular Bayesian Model for de novo Motif Detection (2004)
Eric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp
this paper, we present LOGOS,anintegratedLOcal and GlObal motif Sequence model for biopolymer sequences, which provides a principled framework for developing, modularizing, extending and computing...
Global Synchronization in Sensornets (2004)
Richard Karp Jeremy, Richard M. Karp, Jeremy Elson, Christos H. Papadimitriou, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
MotifPrototyper: a Bayesian Profile Model for Motif Families (2004)
In this paper, we address the problem of modeling generic features of structurally but not textually related DNA motifs, that is, motifs whose consensus sequences are entirely di#erent, but...
Global synchronization in sensornets (2004)
Richard M. Karp, Jeremy Elson, Christos H. Papadimitriou, Scott Shenker
Time synchronization is necessary in many distributed systems, but achieving synchronization in sensornets, which combine stringent precision requirements with severe resource constraints, is...
A hierarchical Bayesian Markovian model for motifs in biopolymer sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
A simple algorithm for finding frequent elements in streams and bags (2003)
Richard M. Karp, Christos H. Papadimitriou, Scott Shenker
Abstract. We present a simple, exact algorithm for iceberg queries (identifying in a multidet the items with frequency more than a threshold ) that requires two passes, linear time, and space 1=. 1.
A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
A hierarchical Bayesian Markovian model for motifs in biopolymer sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
A hierarchical Bayesian Markovian model for motifs in biopolymer sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
A hierarchical Bayesian Markovian model for motifs in biopolymer sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russellcomputer, Science Division
Abstract We propose a dynamic Bayesian model for motifs in biopolymer se-quences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our...
A hierarchical Bayesian Markovian model for motifs in biopolymer sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
Large scale reconstruction of haplotypes from genotype data (2003)
Eleazar Eskin, Eran Halperin, Richard M. Karp
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
LOGOS: A Modular Bayesian Model for de novo Motif Detection (2003)
Eric P. Xing, Wei Wu, Michael I. Jordan, Richard M. Karp
The complexity of the global organization and internal structures of motifs in higher eukaryotic organisms raises significant challenges for motif detection techniques. To achieve successful de novo...
Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani
Micah Adler # Department of Computer Science, University of Massachusetts, Amherst, MA 01003-4610, USA micah@cs.umass.edu Eran Halperin + Science Institute and Computer Science Division University of...
Towards optimally multiplexed applications of universal DNA tag systems (2003)
Amir Ben-dor, Tzvika Hartman, Richard M. Karp, Benno Schwikowski, Roded Sharan, Zohar Yakhini
We study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (SNPs) are to be genotyped using a universal DNA tag array. The problem of optimizing the...
Efficient reconstruction of haplotype structure via perfect phylogeny (2003)
Eleazar Eskin, Eran Halperin, Richard M. Karp
Each person’s genome contains two copies of each chromosome, one inherited from the father and the other from the mother. A person’s genotype specifies the pair of bases at each site, but does...
A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences (2003)
Eric P. Xing, Michael I. Jordan, Richard M. Karp, Stuart Russell
We propose a dynamic Bayesian model for motifs in biopolymer sequences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model...
CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments (2003)
Sharan, Roded, Ovcharenko, Ivan, Ben-Hur, Asa, Karp, Richard M.
Motivation: The binding of transcription factors to specific regulatory sequence elements is a primary mechanism for controlling gene transcription. Recent findings suggest a modular organization of...
Towards optimally multiplexed applications of universal DNA tag systems (2003)
Amir Ben-dor, Tzvika Hartman, Richard M. Karp, Benno Schwikowski, Roded Sharan, Zohar Yakhini
We study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (SNPs) are to be genotyped using a universal DNA tag array. The problem of optimizing the...
Mathematical challenges from genomics and molecular biology (2002)
Afundamental goal of biology is to understand how living cells function. This understanding is the foundation for all higher levels of explanation, including physiology, anatomy, behavior, ecology,...
Feature selection for high-dimensional genomic microarray data (2001)
Eric P. Xing, Michael I. Jordan, Richard M. Karp
We report on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space. Our approach is a...
Feature selection for high-dimensional genomic microarray data (2001)
Eric P. Xing, Michael I. Jordan, Richard M. Karp
We report on the successful application of feature selection methods to a classication problem in molecular biology involving only 72 data points in a 7130 dimensional space. Our approach is a hybrid...
Feature selection for high-dimensional genomic microarray data (2001)
We report on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space. Our approach is a...
Feature selection for high-dimensional genomic microarray data (2001)
Eric P. Xing, Michael I. Jordan, Richard M. Karp
We report on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space. Our approach is a...
We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the...
Feature selection for high-dimensional genomic microarray data (2001)
Eric P. Xing, Michael I. Jordan, Richard M. Karp
We report on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space. Our approach is a...
Xing, Eric P., Karp, Richard M.
We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the...
Discovery of regulatory interactions through perturbation: Inference and experimental design (2000)
Trey E. Ideker, Vesteinn Thorsson, Richard M. Karp
We present two methods to be used interactively to infer a genetic network from gene expression measurements. The predictor method determines the set of Boolean networks consistent with an observed...
Daniel Fasulo, Daniel Fasulo, Richard M. Karp, Walter Ruzzo, Martin Tompa
This is to certify that I have examined this copy of a doctoral dissertation by
ISIT’98 Plenary Lecture Report: Variations on the Theme of ‘Twenty Questions (1999)
This article is based on my plenary talk at the IEEE International Symposium on Information Theory held at M.I.T. in August, 1998. The talk concerned a family of identification problems exemplified...
The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph...
Parallel Sorting with Limited Bandwidth (1999)
Micah Adler, John W. Byers, Richard M. Karp
We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the PRAM(m) model, where p processors communicate through a globally shared memory which can...
Optimizing the BAC-End Strategy for Sequencing the Human Genome (1999)
The rapid increase in human genome sequencing effort and the emergence of several alternative strategies for large-scale sequencing raise the need for a thorough comparison of such strategies. This...
Algorithms for Graph Partitioning on the Planted Partition Model (1999)
The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph...
The Non-Messing-Up Theorem, (1998)
The paper is concerned with the ordering of certain sets in different ways. A typical example is a rectangular array of playing cards which can be ordered so that either (a) the rows are in...
Parallel and Distributed Computing. (1998)
A workshop on the complexity of parallel and distributed computation in May 1986. It has 21 speakers and 141 participants; their interests ranged from practical questions about the architecture of...
Constructing Maps Using the Span and Inclusion Relations (1998)
Dan Fasulo, Tao Jiang, Richard M. Karp, Nitin Sharma
Many computational problems in DNA mapping and sequencing involve determining the relative positions of DNA fragments derived from a target genome region. In the past, many such problems were...
Algorithms for Optical Mapping (1998)
Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The...
Fast and Intuitive Clustering of Web Documents (1997)
Oren Zamir, Oren Etzioni, Omid Madani, Richard M. Karp
Conventional document retrieval systems (e.g., Alta Vista) return long lists of ranked documents in response to user queries. Recently, document clustering has been put forth as an alternative method...
Fast and Intuitive Clustering of Web Documents (1997)
Oren Zamir, Oren Etzioni, Omid Madani, Richard M. Karp
Conventional document retrieval systems (e.g., Alta Vista) return long lists of ranked documents in response to user queries. Recently, document clustering has been put forth as an alternative method...
Fast and Intuitive Clustering of Web Documents (1997)
Oren Zamir, Oren Etzioni, Omid Madani, Richard M. Karp
Conventional document retrieval systems (e.g., Alta Vista) return long lists of ranked documents in response to user queries. Recently, document clustering has been put forth as an alternative method...
Error-Resilient DNA Computation (1997)
Richard M. Karp, Claire Kenyon, Orli Waarts
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, Extract-A-Bit, which splits a test tube into two test tubes according to the value...
Error-resilient DNA computation (1996)
Richard M. Karp, Richard M. Karp, Claire Kenyon, Claire Kenyon, Orli Waarts, Orli Waarts
The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, Extract-A-Bit, Merge-Two-Tubes and Detect-Emptiness. Perfect operations can test...
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1996)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
Error-resilient DNA computation. (1995)
Karp, Richard M., Kenyon, Claire, Waarts, Orli
(eng) The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, extract-a-bit, merge-two-tubes and detect-emptiness. Perfect operations can...
Parallel sorting with limited bandwidth (1995)
Micah Adler, John W Byers, Richard M Karp
We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the recently proposed PRAM(m) model, where p processors communicate through a small, globally...
Parallel Sorting With Limited Bandwidth (1995)
Micah Adler, John W. Byers, Richard M. Karp
We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the recently proposed PRAM(m) model, where p processors communicate through a globally shared...
A Graph-Theoretic Game and its Application to the k-Server Problem (1995)
Noga Alon, Richard M. Karp, David Peleg, Douglas West
This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and...
Scheduling Parallel Communication: The (1995)
Relation Problem Micah, Micah Adler, John W. Byers, Richard M. Karp
. This paper is concerned with the efficient scheduling and routing of point-to-point messages in a distributed computing system with n processors. We examine the h-relation problem, a routing...
Scheduling Parallel Communication: The h-relation Problem (1995)
Micah Adler, John W. Byers, Richard M. Karp
This paper is concerned with the efficient scheduling and routing of point-to-point messages in a distributed computing system with n processors. We examine the h-relation problem, a routing problem...
Probabilistic Analysis of Network Flow Algorithms (1995)
Richard M. Karp, Rajeev Motwani, Noam Nisan
This paper is concerned with the design and probabilistic analysis of algorithms for the maximumflow problem and capacitated transportation problems. These algorithms run in linear time and, under...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? (1995)
Alan Frieze, Richard M. Karp, Bruce Reed
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP (M) and the value of its assignment relaxation AP (M ). We assume here that the...
An Algorithm for Analyzing Probed Partial Digestion Experiments (1995)
Richard M. Karp, Lee A. Newberg
A partial digestion of DNA (e.g., cosmid, Lambda, YAC, chromosome) is performed and the lengths of thoses fragments which hybridize to a labeled probe are measured using gel electrophoresis. We give...
Physical Mapping of Chromosomes Using Unique Probes (1995)
Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig
The goal of physical mapping of the genome is to reconstruct a strand of DNA given a collection of overlapping fragments, or clones, from the strand. We present several algorithms to infer how the...
Selection in the Presence of Noise: The Design of Playoff Systems (1995)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
An algorithm for analysing probed partial digestion experiments (1995)
Karp, Richard M., Newberg, Lee A.
A partial digestion of DNA (e.g. cosmid, Lambda, YAC, chromosome) is performed and the lengths of thoses fragments which hybridize to a labeled probe are measured using gel electrophoresis. We give...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem (1995)
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem AT SP (M) and the value of its assignment relaxation AP (M). We assume here that the...
Coding techniques for handling failures in large disk arrays (1994)
Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, David A. Patterson
Abstract:Abstract: A crucial issue in the design of very large disk arrays is the protection of data against catastrophic disk failures. Although today single disks are highly reliable, when a disk...
Physical Mapping of Chromosomes Using Unique Probes (1994)
Farid Alizadeh, Richard M. Karp, Deborah K. Weisser, Geoffrey Zweig
this paper we present several combinatorial algorithms for reconstructing a DNA strand given a collection of overlapping fragments of the strand. A human chromosome, which is a DNA molecule of about...
Selection in the Presence of Noise: The Design of Playoff Systems (1994)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
Efficient PRAM Simulation on a Distributed Memory Machine (1994)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
Finite Branching Processes and AND/OR Tree Evaluation (1994)
This paper studies tail bounds on supercritical branching processes with finite distributions of offspring. Given a finite supercritical branching process fZ n g 1 0 , we derive upper bounds,...
Selection in the Presence of Noise: The Design of Playoff Systems (1994)
Micah Adler, Peter Gemmell, Mor Harchol, Richard M. Karp, Claire Kenyon
this paper we consider the optimal design of such systems. We seek designs that are optimally efficient, in the sense that they minimize the number of rounds or the number of games needed to select...
Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology (1993)
Farid Alizadeh, Richard M. Karp, Lee A. Newberg, Deborah K. Weisser
This paper is concerned with algorithms for the reassembly process.
Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology (1993)
Farid Alizadeh, Richard M. Karp, Lee A. Newberg, Deborah K. Weisser
This paper is concerned with algorithms for the reassembly process.
Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology (1993)
Farid Alizadeh, Richard M. Karp, Lee A. Newberg, Deborah K., Deborah K. Weisser
A fundamental tool for exploring the structure of a long DNA sequence is to construct a "library" consisting of many cloned fragments of the sequence. Each fragment can be replicated...
Optimal Broadcast and Summation in the LogP Model (1993)
Richard M. Karp, Abhijit Sahay, Eunice E. Santos, Klaus Erik Schauser
In many distributed-memory parallel computers the only built-in communication primitive is point-to-point message transmission, and more powerful operations suchas broadcast and synchronization must...
Efficient PRAM Simulation on a Distributed Memory Machine (1992)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? (1992)
Alan Frieze, Richard M. Karp, Bruce Reed
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP (M) and the value of its assignment relaxation AP (M ). We assume here that the...
Efficient PRAM Simulation on a Distributed Memory Machine (1992)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract) (1991)
Noga Alon, Richard M. Karp, David Peleg
) Noga Alon Richard M. Karp y David Peleg z Douglas West x July 11, 1991 Abstract This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player...
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1991)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
JOURNAL OF ALGORITHMS 12,685-699 (1991) Competitive Paging Algorithms (1988)
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
Coding Techniques for Handling Failures in Large Disk Arrays (1988)
Lisa Hellerstein, Garth A. Gibson, Richard M. Karp, Randy H. Katz, David A. Patterson
:Abstract: A crucial issue in the design of very large disk arrays is the protection of data against catastrophic disk failures. Although today single disks are highly reliable, when a disk array...
Parameter Shortest Path Algorithms with an Application to Cyclic Staffing (1980)
Let G = (V,E) be a digraph with n vertices including a special vertex s. Let E' C E be a designated subset of edges. For each e E E there is an associated real number fl(e). Furthermore, let 1 if e E...
Parameter Shortest Path Algorithms with an Application to Cyclic Staffing (1980)
Let G = (V,E) be a digraph with n vertices including a special vertex s. Let E' C E be a designated subset of edges. For each e E E there is an associated real number fl(e). Furthermore, let 1 if e E...
Karp, Richard M, American Mathematical Society, Society For Industrial And Applied Mathematics
Incluye bibliografía e índice
Selected topics in automata theory (1966)
http://deepblue.lib.umich.edu/bitstream/2027.42/5874/5/bac5556.0001.001.pdf
Conserved pathways within bacteria and yeast as revealed by global protein network alignment
Kelley, Brian P., Sharan, Roded, Karp, Richard M., Sittler, Taylor, Root, David E., Stockwell, Brent R., ...
We implement a strategy for aligning two protein–protein interaction networks that combines interaction topology and protein sequence similarity to identify conserved interaction pathways and...
Thayer, Edward C., Olson, Maynard V., Karp, Richard M.
Genetic and physical maps display the relative positions of objects or markers occurring within a target DNA molecule. In constructing maps, the primary objective is to determine the ordering of...
MotifPrototyper: A Bayesian profile model for motif families
Xing, Eric P., Karp, Richard M.
In this article, we address the problem of modeling generic features of structurally but not textually related DNA motifs, that is, motifs whose consensus sequences are entirely different but...
Conserved patterns of protein interaction in multiple species
Sharan, Roded, Suthram, Silpa, Kelley, Ryan M., Kuhn, Tanja, McCuine, Scott, Uetz, Peter, ...
To elucidate cellular machinery on a global scale, we performed a multiple comparison of the recently available protein–protein interaction networks of Caenorhabditis elegans, Drosophila...
Conserved pathways within bacteria and yeast as revealed by global protein network alignment
Kelley, Brian P., Sharan, Roded, Karp, Richard M., Sittler, Taylor, Root, David E., Stockwell, Brent R., ...
We implement a strategy for aligning two protein–protein interaction networks that combines interaction topology and protein sequence similarity to identify conserved interaction pathways and...
Thayer, Edward C., Olson, Maynard V., Karp, Richard M.
Genetic and physical maps display the relative positions of objects or markers occurring within a target DNA molecule. In constructing maps, the primary objective is to determine the ordering of...
MotifPrototyper: A Bayesian profile model for motif families
Xing, Eric P., Karp, Richard M.
In this article, we address the problem of modeling generic features of structurally but not textually related DNA motifs, that is, motifs whose consensus sequences are entirely different but...
Conserved patterns of protein interaction in multiple species
Sharan, Roded, Suthram, Silpa, Kelley, Ryan M., Kuhn, Tanja, McCuine, Scott, Uetz, Peter, ...
To elucidate cellular machinery on a global scale, we performed a multiple comparison of the recently available protein–protein interaction networks of Caenorhabditis elegans, Drosophila...
eQED: an efficient method for interpreting eQTL associations using protein networks
Suthram, Silpa, Beyer, Andreas, Karp, Richard M, Eldar, Yonina, Ideker, Trey
Analysis of expression quantitative trait loci (eQTLs) is an emerging technique in which individuals are genotyped across a panel of genetic markers and, simultaneously, phenotyped using DNA...
Association Mapping and Significance Estimation via the Coalescent
Kimmel, Gad, Karp, Richard M., Jordan, Michael I., Halperin, Eran
The central questions asked in whole-genome association studies are how to locate associated regions in the genome and how to estimate the significance of these findings. Researchers usually do this...
Torque: topology-free querying of protein interaction networks
Bruckner, Sharon, Hüffner, Falk, Karp, Richard M., Shamir, Ron, Sharan, Roded
Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in...