Problems and Solutions in Biological Sequence Analysis

This book is the first of its kind to provide a large collection of bioinformatics problems with accompanying solutions. Notably, the problem set includes all of the problems offered in Biological Sequence Analysis (BSA), by Durbin et al., widely adopted as a required text for bioinformatics courses at leading universities worldwide. Although many of the problems included in BSA as exercises for its readers have been repeatedly used for homework and tests, no detailed solutions for the problems were available. Bioinformatics instructors had therefore frequently expressed a need for fully worked solutions and a larger set of problems for use on courses. This book provides just that: following the same structure as BSA and significantly extending the set of workable problems it will facilitate a better understanding of the contents of the chapters in BSA and will help its readers develop problem solving skills that are vitally important for conducting successful research in the growing field of bioinformatics. All of the material has been class-tested by the authors at Georgia Tech, where the first ever M.Sc. degree program in Bioinformatics was held. MARK BORODOVSKY is the Regents' Professor of Biology and Biomedical Engineering and Director of the Center for Bioinformatics and Computational Biology at Georgia Institute of Technology in Atlanta. He is the founder of the Georgia Tech M.Sc. and Ph.D. degree programs in Bioinformatics. His research interests are in bioinformatics and systems biology. He has taught Bioinformatics courses since 1994. SVETLANA EKISHEVA is a Research Scientist at the School of Biology, Georgia Institute of Technology, Atlanta. Her research interests are in bioinformatics, applied statistics and stochastic processes. Her expertise includes teaching probability theory and statistics at universities in Russia and in the USA. Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Preface......Page 13 1 Introduction......Page 17 1.1 Original problems......Page 18 1.2 Additional problems......Page 21 1.3 Further reading......Page 39 2.1 Original problems......Page 40 2.2 Additional problems and theory......Page 59 2.2.1 Derivation of the amino acid substitution matrices (PAM series)......Page 62 2.2.2.1 Theoretical introduction to Problems 2.19 and 2.20.......Page 73 2.2.3 Distribution of the length of the longest common word among several unrelated sequences......Page 78 2.3 Further reading......Page 81 3 Markov chains and hidden Markov models......Page 83 3.1 Original problems......Page 84 3.2 Additional problems and theory......Page 93 Theoretical introduction to Problems 3.20 and 3.21......Page 102 Theoretical introduction to Problem 3.23......Page 111 3.3 Further reading......Page 118 4 Pairwise alignment using HMMs......Page 120 4.1 Original problems......Page 121 4.2 Additional problems......Page 129 4.3 Further reading......Page 141 5 Profile HMMs for sequence families......Page 142 5.1 Original problems......Page 143 5.2 Additional problems and theory......Page 153 5.2.1 Discrimination function and maximum discrimination weights......Page 166 5.3 Further reading......Page 177 6 Multiple sequence alignment methods......Page 178 6.2 Additional problems and theory......Page 179 Theoretical introduction to Problem 6.2......Page 180 Theoretical introduction to Problem 6.3......Page 187 6.2.3 Gibbs sampling algorithm for local multiple alignment......Page 195 6.3 Further reading......Page 197 7.1 Original problems......Page 199 7.2 Additional problems......Page 227 7.3 Further reading......Page 231 8 Probabilistic approaches to phylogeny......Page 234 8.1 Original problems......Page 235 8.1.1 Bayesian approach to finding the optimal tree and the Mau--Newton--Larget algorithm......Page 251 8.2 Additional problems and theory......Page 275 8.2.1 Relationship between sequence evolution models described by the Markov and the Poisson processes......Page 280 Theoretical introduction to Problem 8.20......Page 286 8.2.3 More on the rates of substitution......Page 291 8.3 Further reading......Page 293 9 Transformational grammars......Page 295 9.1 Original problems......Page 296 9.2 Further reading......Page 306 10 RNA structure analysis......Page 307 10.1 Original problems......Page 308 10.2 Further reading......Page 324 11.1 Original problems......Page 327 11.2 Additional problem......Page 342 11.3 Further reading......Page 343 References......Page 344 Index......Page 359 This book is the first of its kind to provide a large collection of bioinformatics problems with accompanying solutions. Notably, the problem set includes all of the problems offered in Biological Sequence Analysis, by Durbin et al. (Cambridge, 1998), widely adopted as a required text for bioinformatics courses at leading universities worldwide. Although many of the problems included in Biological Sequence Analysis as exercises for its readers have been repeatedly used for homework and tests, no detailed solutions for the problems were available. Bioinformatics instructors had therefore frequently expressed a need for fully worked solutions and a larger set of problems for use on courses. This book provides just that: following the same structure as Biological Sequence Analysis and significantly extending the set of workable problems, it will facilitate a better understanding of the contents of the chapters in BSA and will help its readers develop problem-solving skills that are vitally important for conducting successful research in the growing field of bioinformatics. All of the material has been class-tested by the authors at Georgia Tech, where the first ever MSc degree program in Bioinformatics was held. Biological Sequence Analysis (BSA) by Durbin et al has become almost the defacto standard textbooy for teaching bioinformatics. And like most texts it presents a series of problems for the student to solve. Because of the rapid growth of bioinformatics, the schools have attracted a large number of students that have come from a wide variety of educational backgrounds. As a result, the presumptions made by the authors on the mathematical ability of the students studying BSA is at variance from the students now using the book. This book is intended to provide these students with a 'cram course' in the mathematics they will need to tackle the BSA problems. It starts by providing detailed solutions to the problems presented in BSA, it then extends the set of workable problems to further develop the problem solving skills of the students. This book might be viewed as a 360 page supplement to BSA. It's mathematics is not trivial, but is necessary for the student to succeed in the bioinformatics field. It is a book that the unprepared student will spend many hours studying. This companion to the highly successful textbook, Biological Sequence Analysis by Durbin et al. (Cambridge, 1998), provides fully worked solutions to the original problems as well as new, fully worked problems. Together these will enable students to develop the problem solving skills that are essential for conducting successful research in the field of bioinformatics. The reader will quickly discover that the organization of this book was chosen to be parallel to the organization of Biological Sequence Analysis by Durbin et al. (1998). Companion to Biological Sequence Analysis, providing solutions to the original problems and additional worked examples