生物信息学算法入门

5星 · 超过95%的资源需积分: 50 174 浏览量更新于2024-07-25 1 收藏 5.98MB PDF 举报

"An Introduction to Bioinformatics Algorithms" 是一本由 Neil C. Jones 和 Pavel A. Pevzner 合著的关于生物信息学算法的入门书籍，由 Sorin Istrail, Pavel Pevzner, 和 Michael Waterman 编辑。这本书是 MIT Press Series on Computational Molecular Biology 系列的一部分，该系列旨在快速出版高质量的专著、教科书、合集、参考作品和讲义，以促进分子生物学领域的新技术和工具的发展。生物信息学是计算科学、统计学、实验方法和技术的交叉学科，它为分子生物学的研究注入了新的活力，并显著加快了新发现的速度。本书作为算法角度的计算分子生物学介绍，主要关注如何使用计算机科学的方法来解决生物学问题。书中可能涵盖了以下几个核心知识点： 1. **序列比对**：这是生物信息学的基础，包括全局比对和局部比对，如Smith-Waterman算法和Needleman-Wunsch算法，用于比较DNA、RNA或蛋白质序列以寻找相似性。 2. **基因预测**：预测DNA序列中的编码区域，如Glimmer和GenScan等工具，是研究基因结构和功能的重要步骤。 3. **进化树构建**：通过计算序列间的距离矩阵，使用UPGMA、NJ（ Neighbor Joining）等方法构建物种或基因的进化关系树。 4. **基因组组装**：从短读测序数据中重建完整基因组，涉及De Bruijn图和基于重叠群的组装算法，如Velvet和SPAdes。 5. **蛋白质结构预测**：利用二级结构预测（如PSIPRED）、三级结构预测（如Phyre2和Rosetta）以及折叠识别方法。 6. **生物网络分析**：包括基因调控网络、代谢网络的构建与分析，如使用图论和动力系统模型来理解复杂生物系统的动态行为。 7. **微阵列数据分析**：处理高通量基因表达数据，用以识别基因表达模式和差异表达基因，如LIMMA和SAM方法。 8. **生物信息学数据库和在线工具**：介绍如何利用NCBI、Ensembl、UniProt等公共数据库以及BLAST、InterProScan等在线工具进行数据分析。 9. **机器学习和统计方法**：在生物信息学中的应用，如支持向量机（SVM）在分类和预测问题中的使用，以及贝叶斯网络在不确定性建模中的角色。 10. **后基因组计算方法**：随着高通量测序技术的发展，探讨了如何处理海量的后基因组数据，如ChIP-seq和RNA-seq数据分析。 "An Introduction to Bioinformatics Algorithms" 是一本全面介绍生物信息学中核心算法的教材，适合生物学、计算机科学和统计学背景的读者学习，以掌握如何运用计算方法解决生物学难题。

Preface

In the early 1990s when one of us was teaching his ﬁrst bioinformatics class,

he was not sure that there would be enough students to teach. Although

the Smith-Waterman and BLAST algorithms had already been developed

they had not become the household names among biologists that they are

today. Even the term “bioinformatics” had not yet been c oined. DNA arrays

were v ie wed by most as intellectual toys with dubious practical application,

except for a handful of e nthusiasts who saw a vast potential in the technol-

ogy. A few bioinformaticians were developing new algorithmic ideas for

nonexistent data sets: David Sankoff laid the foundations of genome rear-

rangement studies at a time when there was practically no gene order data,

Michael Waterman and Gary Stormo were developing motif ﬁnding algo-

rithms when there were very few promoter samples a v ailable, Gene Myers

was dev eloping sophisticated fragment assembly tools when no bacterial

genome ha s been assembled yet, and Webb Miller was dreaming about com-

paring billion-nucleotide-long DNA sequences when the 172, 282-nucleotide

Epstein-Barr virus was the longest GenBank entry. GenBank itself just re-

cently made a transition from a series of bound (paper!) volumes to an elec-

tronic database on magnetic tape that could be sent to scientists worldwide.

One has to go back to the mid-1980s and early 1990s to fully appreciate the

revolution in biology that has taken place in the last decade. However, bioin-

formatics has affected more than just biology—it has a lso had a profound

impact on the computational sciences. Biology has rapidly become a large

source of new algorithmic and statistical problems, and has arguably been

the target for more algorithms than any of the other fundamenta l sciences.

This link between computer science and biology has important educational

implications that change the way we teach computational ideas to biologists,

as well as how applied algorithmics is taught to computer scientists.

xvi Preface

For ma ny years computer science was taught to only computer scientists,

and only rarely to students from other disciplines. A biology student in an al-

gorithms class would be a surprising and unlikely (though entirely welcome)

guest in the early 1990s. But these things change; many b iology students

now take some sort of Algorithms 101. At the same time, curious computer

science students often take Genetics 101 and Bioinformatics 101. Although

these students are still relatively r are, keep in mind that the number of b ioin-

formatics cla sses in the early 1990s was so small as to be considered nonexis-

tent. But that number is not so small now. We envision that undergraduate

bioinformatics classes will become a per manent component at every major

university. This is a feature, not a bug.

This is a n introductory textbook on bioinformatics algorithms and the com-

putational ideas that have driven them through the last twenty years. There

are many important probabilistic and statistical te chniques that we do not

cover, nor do we cover many important research questions that bioinfor-

maticians are c ur rently trying to answer. We deliberately do not cover all

areas of computational b iology; for example, important topics like protein

folding are not even discussed. The very ﬁrst b ioinformatics textbooks were

Waterman, 1995 (108), which contains ex cellent coverage of DNA statistics

and Gusﬁeld, 1997 (44) which includes an encyclopedia of string algorithms.

Durbin e t al., 1998 (31) and Baldi and Brunak, 1997 (7) emphasize Hidden

Markov Models and machine learning techniques; Baxevanis and Ouellette,

1998 (10) is an excellent practical guide to bioinformatics; Mount, 2001 (76)

excels in showing the connections between biological problems a nd bioin-

formatics techniques; and Bourne and Weissig, 2002 (15) focuses on protein

bioinformatics. There are also excellent web-based lecture notes for many

bioinformatics courses and we lear ned a lot about the pedagogy of bioinfor-

matics from materials on the World Wide Web by Seraﬁm Batzoglou, Dick

Karp, Ron Shamir, Martin Tompa, and others.

Website

We have created an extensive website to accompany this book at

http://www.bioalgorithms.info

This website contains a number of features that complement the book. For

example, though this b ook does not c ontain a glossary, we provide this ser-

vice, a searchable index, and a set of community message boards, at the

above web add ress. Technically savvy students can also download practical

Preface xvii

bioinformatics exercises, sample implementations of the algorithms in this

book, and sample d ata to test them with. Instructors and students may ﬁnd

the prepackaged lecture notes on the website to be especially helpful. It is

our hope tha t this website be used as a repository of information that will

help introduce students to the diverse world of bioinformatics.

Acknowledgements

We are indebted to those who kindly agreed to be featured in the biograph-

ical sketches scattered throughout the book. Their insightful and heartfelt

responses deﬁnitely made these the most interesting part of this book. Their

life stories and views of the challenges that lay ahea d will undoubtedly in-

spire students in the exploration of the unknown. There are ma ny more sci-

entists whose bioboxes we would like to have in this book and it is only

the page limit (which turned out to be 200 page s too small) that prevented

us from commissioning more of them. Special thanks go to Ethan Bier who

inspired us to include biographical sketches in this book.

This book would not hav e been possible without the d iligent tea ching as-

sistants in bioinformatics courses taught during the winter and fall of 2003

and 2004: Derren Barken, Bryant Forsgren, Eugene Ke, C oleman Mosley, and

Degui Zhi all helped ﬁnd technical errors, reﬁne practical exercises, and de-

sign problems in the book. Helen Wu and John Allison spent ma ny hours

making technical ﬁgures, which is a thankless task like no other. We a re also

grateful to Vagisha Shar ma who was kind enough to read the book from

cover to cover and provide insightful comments and, unfortunately, bugs in

the pseudocode. Ste v e Wasserman provided us with invaluable comments

from a biologist’s point of view that eventually le d to new sections in the

book. Alkes Price and Ha ixu Ta ng pointed out ambiguities and helped clar-

ify the chapters on graphs and clustering. Ben Raphael and Patricia Jones

provided feedback on the early chapters and helped avoid some potential

misunderstandings. Dan Gilbert, of Dan Gilbert Art Group, Inc. kindly pro-

vided us with Tr iazzles to illustrate the problems of DNA sequence assembly.

Our special thanks go to Randall Christopher, the artist behind the website

www.kleemanandmike.com. Randall illustrated the book and designed

many unique graphical representations of some bioinformatics algorithms.

It ha s been a pleasure to work with Robert Prior of T he MIT Press. With

sufﬁcient patience and prodding, he managed to keep us on tr ack. We also

appreciate the meticulous copyediting of G. W. Helfrich.

剩余454页未读，继续阅读

yezhengtang

粉丝: 3

生物信息学算法入门

introduction to bioinformatics algorithms

Introduction to Algorithms

Introduction to Algorithm

An introduction to bioinformatics algorithms(生物信息学算法导论)

生物信息学算法导论（an-introduction-to-bioinformatics-algorithms）

Bioinformatics Algorithms 教程及答案

Introduction to Algorithms Lecture Notes (MIT 6.006)

Introduction to Machine Learning (2014)

Time Series Causal Relationship Analysis: An Expert Guide to Identification and Modeling

MATLAB Constrained Optimization: A Dual Strategy of Algorithms and Practices

最新资源