Sequence Analysis -- Introduction: Biological Sequences -- Sequence Alignment -- Markov Chains and Hidden Markov Models -- Protein Folding -- Phylogenetic Reconstruction -- Mathematical Background for Sequence Analysis -- Elements of Probability Theory -- Significance of Sequence Alignment Scores -- Elements of Statistics -- Substitution Matrices. toMathematical Methodsin Bioinformatics With 76 Figures and 3 Tables Alexander Isaev Australian National University Department of Mathematics Canberra, ACT 0200 Australia e-mail: alexander. isaev@maths. anu. edu. au Corrected Second Printing 2006 Mathematics Subject Classi?cation (2000 ): 91 -01 (Primary) 91 D20 (Secondary) Libraryof Congress Control Number: 2006930998 ISBN: 3-540 -21973 -0 ISBN: 9783540219736 This work is subject to copyright. All rights are reserved, whether the whole or part of the mat- ial is concerned, speci?cally the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on micro?lm or in any other way, and storage in data banks. Dup- cation of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9 , 1965 , in its current version, and permission for use must always beobtainedfromSpringer. ViolationsareliableforprosecutionundertheGermanCopyrightLaw. Springer is a part of Springer Science+Business Media springer. com Springer-Verlag Berlin Heidelberg 2006 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a speci?c statement, that such names are exempt from the re- vant protective laws and regulations and therefore free for general use. Cover design: Erich Kirchner, Heidelberg A Typesetting by the author and SPi using a Springer LT X macro package E Printed on acid-free paper: SPIN:11809142 41 /2141 /SPi-543210 To Esya and Masha Preface Broadly speaking, Bioinformatics can be de?ned as a collection of mathema- cal, statistical and computational methods for analyzing biological sequences, thatis,DNA,RNAandaminoacid(protein)sequences.