密码学与生物信息学算法导论

需积分: 0 201 浏览量更新于2024-07-23 收藏 5.38MB PDF 举报

"这篇论文主要涉及密码学领域，适合密码学理论研究者阅读。" 这篇论文的主题是密码学，它在信息安全、数据保护和网络安全中扮演着至关重要的角色。密码学是一门结合数学、计算机科学和通信理论的学科，旨在设计和分析确保数据安全性的方法。在现代社会，随着数字化信息的爆炸性增长，密码学的重要性日益凸显，因为它能够提供加密、认证、完整性和不可否认性等关键服务。论文可能涵盖了密码学的基本概念，如对称加密和非对称加密。对称加密使用相同的密钥进行加密和解密，例如DES（数据加密标准）和AES（高级加密标准），这种加密方式效率高，但密钥管理和分发较为复杂。非对称加密，如RSA和ECC（椭圆曲线加密），使用一对公钥和私钥，公钥可公开，私钥则需要保密，解决了密钥交换的问题，但计算成本相对较高。此外，论文可能还讨论了哈希函数，这是密码学中的一个重要工具，用于创建数据的固定长度摘要，如MD5和SHA系列。哈希函数在数字签名、消息认证码（MAC）和防止篡改等方面有着广泛的应用。密码学也包括了公钥基础设施（PKI）和证书权威机构（CA），这些是现代网络中确保身份验证和安全通信的基础。另外，可能还会涉及零知识证明，这是一种允许一方证明他们知道一个秘密给另一方，而无需揭示该秘密本身的协议。在密码学的现代应用中，可能涵盖了量子密码学，这是一门利用量子力学原理来保证通信安全的新兴领域，如BB84协议和量子密钥分发，它们有望抵御未来量子计算机对传统加密算法的潜在威胁。此外，论文可能探讨了密码学在区块链技术中的应用，如比特币和其他加密货币的加密机制，以及智能合约的安全性。密码学也在物联网（IoT）、云计算和大数据等领域发挥着重要作用，确保大量数据在传输和存储过程中的安全性。这篇密码学论文为读者提供了深入理解这一领域理论和实践的关键洞察，对于密码学研究者和相关领域的专业人士来说，是宝贵的参考资料。

xviii Preface

Finally, we thank the many students in different unde rgraduate and grad-

uate bioinformatics classes at UCSD who provided comments on earlier ver-

sions of this book.

PAP would like to thank se v eral people who taught him different aspects

of computational molecular biology. Andrey Mironov taught him that com-

mon sense is perhaps the most important ingredient of a ny applied research.

Mike Waterman was a terriﬁc teacher at the time PAP moved from Moscow

to Los Angeles, both in science and in life. PAP also thanks Alexander Kar-

zanov, who taught him combinatorial optimization, which, s ur p risingly, re-

mains the most useful set of skills in his computational biology research. He

especially thanks Mark Borodovsky who convinced him to switch into the

ﬁeld of bioinformatics in 1985, when it was an obscure discipline with a n

uncertain future.

PAP also thanks his former students, postdocs, and lab members who

taught him most of what he knows: Vineet Baf na, Guillaume B ourque, Srid-

har Hannenhalli, Steffen Heber, Earl Hubbell, Uri Keich, Zufar Mulyukov,

Alkes Price, Ben Raphael, Sing-Hoi Sze, Haixu Tang, and Glenn Tesler.

NCJ would like to thank his mentors during undergraduate school— Toshi-

hiko Takeuchi, Harry Gray, John Baldeschwieler, and Schubert Soares—for

patiently b ut ﬁrmly teaching him that persistence is one of the more impor-

tant ingredients in research. Also, he thanks the admissions committee at the

University of California, San Diego who gambled on a chemist-turned-pro-

grammer, hopefully for the best.

Neil Jones and Pavel Pevzner

La Jolla, California, 2004

2 1 Introduction

Moreover, she took Algorithms 101 and she understands that recipes written

in the style that Bob uses will not help very much: recipe-style instructions

are not a sufﬁciently expressive language for d escribing algorithms. Instead,

she be gins by drawing the following table ﬁlled with the symbols ↑, ←, -,

and ∗. The entry in position (i, j) (i.e., the ith row and the jth column) de-

scribes the moves that Alice will make in the i + j game, with i and j rocks

in piles A and B respectively. A ← indicates that she should take one stone

from pile B. A ↑ indicates that she should take one stone from pile A. A

- indicates that she should take one stone from each pile, and ∗ indicates

that she should not bother playing the game because she will d eﬁnitely lose

against an opponent who has a clue.

0 1 2 3 4 5 6 7 8 9 10

0 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

1 ↑ - ↑ - ↑ - ↑ - ↑ - ↑

2 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

3 ↑ - ↑ - ↑ - ↑ - ↑ - ↑

4 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

5 ↑ - ↑ - ↑ - ↑ - ↑ - ↑

6 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

7 ↑ - ↑ - ↑ - ↑ - ↑ - ↑

8 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

9 ↑ - ↑ - ↑ - ↑ - ↑ - ↑

10 ∗ ← ∗ ← ∗ ← ∗ ← ∗ ← ∗

For example, if she is f aced with the 3 +3 game, she ﬁnds a - in the third

row and third column, indicating that she should take a rock from each p ile.

This makes Bob take the ﬁrst move in a 2+2 game, which is marked with

a ∗. No matter what he does, Alice wins. Suppose Bob takes a rock from

pile B—this leads to the 2+1 game. Alice again consults the table by reading

the entry at ( 2,1), seeing that she should also take a rock from pile B leaving

two rocks in A. However, if Bob had instead taken a rock from pile A, Alice

would consult entry (1,2) to ﬁnd ↑. She again should also take a rock from

pile A, leaving two rocks in pile B.

Impressed by the ta b le , Bob learns how to use it to win the 10+10 game.

However, Bob does not know how to construct a similar table for the 20+20

game. The problem is not that Bob is stupid, but that he ha s not studied

algorithms. Even if, through sheer luck, Bob ﬁgured how to always win the

1 Introduction 3

20+20 game, he could neither say with conﬁdence that it would work no

matter what Alice did, nor would he even be ab le to write down the recipe

for the general n + n game. More embarrassing to Bob is that the a general

10+10+10 game with three piles would turn into an impossible conundrum

for him.

There are two things Bob could d o to remedy his situation. First, he could

take a class in algorithms to learn how to solve problems like the rock puzzle.

Second, he could memorize a suitably large table that Alice gives him and

use that to play the game. Leading questions notwithstanding, what would

you do as a biologist?

Of course, the answer we expect to hear from most rational people is “Why

in the world do I care about a game with two nerdy people and a bunch of

rocks? I’m interested in biology, and this game has nothing to do with me.”

This is not actually true: the rock game is in fact the ubiquitous sequence

alignment problem in disguise. Although it is not immediately clear what

DNA sequence alignment and the rock game have in common, the compu-

tational idea used to solve both problems is the same. The fact that Bob was

not able to ﬁnd the strategy for the game indicates that he does not under-

stand how alignment algorithms work either. He might disagree if he uses

alignment algorithms or BLAST

on a daily basis, but we argue that since he

failed to come up with a strate gy for the 10+10 rock game, he will also fail

when confronted with a new ﬂavor of alignment problem or a particularly

complex similarity analysis. More troubling to Bob, he may ﬁnd it difﬁcult

to compete with the scads of new biologists who think a lgorithmically about

biological problems.

Many biologists are comfortable using algorithms like BLAST without re-

ally understanding how the underlying algorithm works. T his is not sub-

stantially different from a diligent robot following Alice’s winning strategy

table, but it does hav e an important consequence. BLAST solves a particular

problem only approximately and it has certain systematic weaknesses. We ’re

not picking on BLAST here: the reason that BLAST has these limitations is, in

part, because of the particular problem that it solves. Users who do not know

how BLAST works might misapply the a lgorithm or misinterpret the results

it returns. Biologists sometimes use bioinformatics tools simply as compu-

tational p rotocols in quite the same way that an uninformed mathematicia n

1. BLAST is a database search tool—a Google for biological sequences—that will be introduced

later in this book.

2. These “new biologists” have probably already found another even more elegant solution of

the rocks problem that does not require the construction of a table.

4 1 Introduction

might use experimental protocols without any background in biochemistry

or molecular biology. In either case, important observations might be missed

or incorrect conclusions drawn. Besides, intellectually interesting work can

quickly become mere drudgery if one does not really understand it.

Many recent bioinformatics books cater to this sort of protocol-centric prac-

tical approach to bioinformatics. They focus on parameter settings, speciﬁc

features of application, and other details without revealing the ideas behind

the algorithms. This trend often follows the tradition of biology books of

presenting material as a collection of facts and discoveries. In contrast, intro-

ductory books in algorithms usually f ocus on ideas rather than on the details

of computational recipes.

Since bioinformatics is a computational science, a bioinformatics textbook

should strive to present the principles that drive an algorithm’s design, rather

than list a stamp collection of the algorithms themselves. We hope that de-

scribing the intellectual content of bioinformatics will help retain your inter-

est in the subject. In this book we attempt to show that a handful of algorith-

mic ideas can be used to solve a large number of bioinformatics problems.

We feel that focusing on ideas has more intellectual value and represents

a better long-term investment: protocols change quickly, but the computa-

tional ideas don’t seem to.

We pursued a goal of presenting b oth the foundations of algorithms and

the important results in bioinformatics under the same cover. A more thor-

ough approach for a student would be to take an Introduction to Algorithms

course followed by a Bioinformatics course, but this is often an unrealistic ex-

pectation in view of the heavy course load biologists have to ta ke . To make

bioinformatics ideas accessible to biologists we appeal to the innate algorith-

mic intuition of the student and try to avoid tedious proofs. The technical

details are hidden unless they are absolutely necessary.

This book covers both new and old areas in computational biology. Some

topics, to our knowledge, have never been discussed in a te xtbook before,

while others are relatively old-fashioned and describe some experimental

approaches that are r arely used these days. The reason for including older

topics is twofold. First, some of them still remain the best ex amples for in-

troducing algorithmic ide as. Second, our goal is to show the progression of

ideas in the ﬁeld, with the implicit warning that hot areas in bioinformatics

seem to come and go with alarming speed.

3. In some places we hide important computational and biological details and try to simplify

the presentation. We will unavoidably be blamed later for “trivializing” bioinformatics.

剩余451页未读，继续阅读

abiaojack

粉丝: 0
资源: 1

密码学与生物信息学算法导论

密码学课程设计 密码学 密码学论文 密码学代买 RSA DES

有关密码学论文的一些资料

密码学论文，密码学实验，特经典！

密码学论文的实验报告

密码学论文的一些资料2

密码学论文（英文2）

计算机安全和密码学论文.doc

MERKLE 的1990年经典密码学论文

关于布尔函数设计准则的密码学论文

密码学论文 how to share a secret with cheaters

最新资源

密码学课程设计密码学密码学论文密码学代买 RSA DES