List of works - Richard M. Karp

Conserved patterns of protein interaction in multiple species

scientific article

Conserved pathways within bacteria and yeast as revealed by global protein network alignment

scientific article

eQED: an efficient method for interpreting eQTL associations using protein networks

scientific article published on 4 March 2008

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

scientific article

DEGAS: de novo discovery of dysregulated pathways in human diseases

scientific article

Efficient algorithms for detecting signaling pathways in protein interaction networks

scientific article published in March 2006

Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data

scientific article

CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments

scientific article

The Traveling-Salesman Problem and Minimum Spanning Trees

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

article

Genome-wide association data reveal a global map of genetic interactions among protein complexes

scientific article

A randomization test for controlling population stratification in whole-genome association studies

scientific article

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

scientific article (publication date: April 1972)

Efficient reconstruction of haplotype structure via perfect phylogeny

scientific article

Reducibility among combinatorial problems

scientific article by Richard M. Karp

Efficient randomized pattern-matching algorithms

scholarly article by Richard M. Karp & Michael O. Rabin published March 1987 in IBM Journal of Research and Development

Comparing protein interaction networks via a graph match-and-split algorithm

scientific article published in September 2007

Karp's 21 NP-complete problems

set of computational problems

MotifPrototyper: a Bayesian profile model for motif families

scientific article (publication date: 20 July 2004)

A Dynamic Programming Approach to Sequencing Problems

Logos: a modular bayesian model for de novo motif detection

scientific article published in March 2004

Topology-free querying of protein interaction networks

scientific article published in March 2010

HAPLOPOOL: improving haplotype frequency estimation through DNA pools and phylogenetic modeling

scientific article published on 25 September 2007

Reconstructing Boolean Models of Signaling

scientific article published on January 3, 2013

A simple algorithm for finding frequent elements in streams and bags

article

Pedigree Reconstruction Using Identity by Descent

scientific article published on October 28, 2011

LOGOS: a modular Bayesian model for de novo motif detection

scientific article

Association mapping and significance estimation via the coalescent

scientific article

TORQUE: topology-free querying of protein interaction networks

scientific article published on 2 June 2009

On the Computational Complexity of Combinatorial Problems

The traveling-salesman problem and minimum spanning trees: Part II

scientific article published in 1971

Algorithms to Detect Multiprotein Modularity Conserved during Evolution

scientific article published on July 1, 2012

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

scientific article published in 1977

Haplotype inference in complex pedigrees

scientific article published in March 2010

Optimization criteria and biological process enrichment in homologous multiprotein modules

scientific article (publication date: 25 June 2013)

The restriction scaffold problem

scientific article

The rank of sparse random matrices over finite fields

journal article from 'Random Struct. Algorithms' published in 1997

Rapid identification of repeated patterns in strings, trees and arrays

Some connections between nonuniform and uniform complexity classes

scientific article published in 1980

Universal DNA tag systems

article

On the complexity of unsatisfiability proofs for random k-CNF formulas

article

Comparing Pedigree Graphs

scientific article published on August 16, 2012

Random walks, universal traversal sequences, and the complexity of maze problems

article published in 1979

The complexity of testing whether a graph is a superconcentrator

scientific article published in 1981

Parametric shortest path algorithms with an application to cyclic staffing

Feature selection for high-dimensional genomic microarray data

2001 scholarly article by Xing, Jordan and Karp on genomic feature selection

Keynote address: the role of algorithmic research in computational genomics

scientific article published in January 2003

When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

article by Alan M. Frieze et al published June 1995 in SIAM Journal on Computing

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities

scientific article published in 1996

List of works by Richard M. Karp

Conserved patterns of protein interaction in multiple species

Conserved pathways within bacteria and yeast as revealed by global protein network alignment

eQED: an efficient method for interpreting eQTL associations using protein networks

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

DEGAS: de novo discovery of dysregulated pathways in human diseases

Efficient algorithms for detecting signaling pathways in protein interaction networks

Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data

CREME: a framework for identifying cis-regulatory modules in human-mouse conserved segments

The Traveling-Salesman Problem and Minimum Spanning Trees

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

Genome-wide association data reveal a global map of genetic interactions among protein complexes

A randomization test for controlling population stratification in whole-genome association studies

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Efficient reconstruction of haplotype structure via perfect phylogeny

Reducibility among combinatorial problems

Efficient randomized pattern-matching algorithms

Comparing protein interaction networks via a graph match-and-split algorithm

Karp's 21 NP-complete problems

MotifPrototyper: a Bayesian profile model for motif families

A Dynamic Programming Approach to Sequencing Problems

Logos: a modular bayesian model for de novo motif detection

Topology-free querying of protein interaction networks

HAPLOPOOL: improving haplotype frequency estimation through DNA pools and phylogenetic modeling

Reconstructing Boolean Models of Signaling

A simple algorithm for finding frequent elements in streams and bags

Pedigree Reconstruction Using Identity by Descent

LOGOS: a modular Bayesian model for de novo motif detection

Association mapping and significance estimation via the coalescent

TORQUE: topology-free querying of protein interaction networks

On the Computational Complexity of Combinatorial Problems

The traveling-salesman problem and minimum spanning trees: Part II

Algorithms to Detect Multiprotein Modularity Conserved during Evolution

Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

Haplotype inference in complex pedigrees

Optimization criteria and biological process enrichment in homologous multiprotein modules

The restriction scaffold problem

The rank of sparse random matrices over finite fields

Rapid identification of repeated patterns in strings, trees and arrays

Some connections between nonuniform and uniform complexity classes

Universal DNA tag systems

On the complexity of unsatisfiability proofs for random k-CNF formulas

Comparing Pedigree Graphs

Random walks, universal traversal sequences, and the complexity of maze problems

The complexity of testing whether a graph is a superconcentrator

Parametric shortest path algorithms with an application to cyclic staffing

Feature selection for high-dimensional genomic microarray data

Keynote address: the role of algorithmic research in computational genomics

When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities

The Efficiency of Resolution and Davis--Putnam Procedures