Karp说：“从我进入大学开始，就非常着迷于组合数学算法。这些类似猜谜的问题涉及在有限但海量的可能性集合中寻找模式或结构来满足一定的限制或者用最小的代价。例如，在生物信息中，包含序列联配，多序列比对，系统发生树构建，基因组重组分析和基因调控模型。对一些组合问题，有精致和有效率的算法来象钟表工作一样进行，就可以得到所需要的结果。可是大多问题是不易处理的，不是需要非常长的计算时间，就是需要折中到一个不是最优化的解。”

1972年，Karp发展了一种途径来显示许多看上去很难的组合问题要么都是，要么都不是有效率可解的意义上是等价的（一个问题称为有效率可解，定义为存在一个多项式时间的算法来解决的问题）。这些问题称之为NP-完全性问题。经过多年研究，成千个例子已经被加入到他提出的21个NP-完全问题的列表。但是尽管他用了彻底的努力，没有一个这样的问题显示出能有效率可解。许多计算机学家（包括Karp）相信他们无一有效率可解。

Karp开始生物信息学研究是1991年前后，他是被简短的计算方法可能揭示生命机体内部工作的秘密所吸引来的。他说：

“我希望我在研究组合算法中的经验可以对破解这些秘密有所帮助。我确实能够在这个新领域利用我的技巧，但只有在能够理解要解决的生物问题时才行，需要远比聪明的算法要重要。它涉及到在生物学和计算机科学家之间的一种有创造力的伙伴关系，这才能够得到一个适当的数学模型，认识和运用多方面的数据源，以及恰当的统计方法（这种统计方法可以来显示我们发现的生物图谱和规律不是随机出现的）。我最近的工作是关于分析基因转录调控，发现保守的调控路径和分析人类的遗传多样性。

自1991年以来，生物学有了惊人地进步，大多数著名的物种的基因组已经被测序。我相信我们正处在理解（可能甚至是改编）那些控制细胞过程的基因调控网络和代谢网络。通过比较许多相关生物的基因组，我们希望理解这些网络是怎样进化的。事实上，我们正尽力寻找复杂疾病的遗传基础，以便我们发展更有效的治疗方式。”

原文：

Richard Karp, born 1935 in Boston, is a Professor at the University of California at Berkeley, with a principal appointment in computer science and additional appointments in mathematics, bioengineering, and operations research. He attended Boston Latin School and Harvard University, where he received a PhD in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department of the IBM Research Center in Yorktown Heights, NY.He has been a faculty member at the University of California at Berkeley since 1968 (with the exception of the period 1995–99, when he was a professor at the University of Washington). Since 1988 he has also been a research scientist at the International Computer Science Institute, a non-profit research company in Berkeley. Karp says:
   Ever since my undergraduate days I have had a fascination with combinatorial algorithms. These puzzle-like problems involve searching through a finite but vast set of possibilities for a pattern or structure that meets certain requirements or is of minimum cost. Examples in bioinformatics include sequence assembly, multiple alignment of sequences,phylogeny construction, the analysis of genomic rearrangements, and the modeling of gene regulation. For some combinatorial problems, there are elegant and efficient algorithms that proceed like clockwork to find the required solution, but most are less tractable and require either a very long computation or a compromise on a solution that may not be optimal.

In 1972, Karp developed an approach to showing that many seemingly hard combinatorial problems are equivalent in the sense that either all of them or none of them are efficiently solvable (a problem is considered efficiently solvable if it can be solved by a polynomial algorithm). These problems are the “NP-Complete” problems. Over the years, thousands of examples have been added to his original list of twenty-one NP-complete problems, yet despite intensive effort none of these problems has been shown to be efficiently solvable. Many computer scientists (including Karp) believe that none of them ever will be.
    Karp began working in bioinformatics circa 1991, attracted by the belief that computational methods might reveal the secret inner workings of living organisms. He says:
    [I hoped] that my experience in studying combinatorial algorithms could be useful in cracking those secrets. I have indeed been able to apply my skills in this new area, but only after coming to understand that
solving biological problems requires far more than clever algorithms: it involves a creative partnership between biologists and mathematical scientists to arrive at an appropriate mathematical model, the acquisition
and use of diverse sources of data, and statisticalmethods to show that the biological patterns and regularities that we discover could not be due to chance. My recent work is concerned with analyzing the transcriptional regulation of genes, discovering conserved regulatory pathways, and analyzing genetic variation in humans.
    There have been spectacular advances in biology since 1991, most notable being the sequencing of genomes. I believe that we are now poised to understand—and possibly even reprogram— the gene regulatory networks and the metabolic networks that control cellular processes. By comparing many related organisms, we hope to understand how these networks evolved. Effectively, we are trying to find the genetic basis of complex diseases so that we can develop more effective modes of treatment.