462 citations · 783 across the 9 of their papers we have counts for
5 papers · 1 filter
Faster and More Accurate Sequence Alignment with SNAP
Matei Zaharia, William J. Bolosky, Kristal Curtis +6
We present the Scalable Nucleotide Alignment Program (SNAP), a new short and long read aligner that is both more accurate (i.e., aligns more reads with fewer errors) and 10-100x fa…
Algorithms for Implicit Hitting Set Problems
Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno +1
A hitting set for a collection of sets is a set that has a non-empty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardi…
Comparing Pedigree Graphs
Bonnie Kirkpatrick, Yakir Reshef, Hilary Finucane +3
Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child.…
Sorting and Selection in Posets
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel +2
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…
Competitive Paging Algorithms
Amos Fiat, Richard Karp, Mike Luby +3
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. This paper introduces the marking algorithm, a sim…