ALGORITHMS IN COMPUTATIONAL BIOLOGY
CONTENTS INTRODUCTION COMPUTATIONAL BIOLOGY BIOLOGICAL SEQUENCES OUTLINE OF THESIS I OVERVIEW COMPARISON OF SEQUENCES COMPARISON OF TWO SEQUENCES EVOLUTIONARY MODELS PAIRWISE ALIGNMENT COMPARISON OF MORE SEQUENCES MULTIPLE ALIGNMENT HIDDEN MARKOV MODELS REGULARITIES IN SEQUENCES TOOLS AND TECHNIQUES TRIES AND SU?X TREES BOUNDING TRAVERSAL TIME MERGING HEIGHT-BALANCED TREES FINDING REGULARITIES TANDEM REPEATS MAXIMAL PAIRS MAXIMAL QUASIPERIODICITIES PREDICTION OF STRUCTURE FREE ENERGY MODELS RNA SECONDARY STRUCTURE PREDICTION PROTEIN TERTIARY STRUCTURE PREDICTION MODELING PROTEIN STRUCTURE APPROXIMATING PROTEIN STRUCTURE IX II PAPERS COMPARISON OF CODING DNA THE DNA/PROTEIN MODEL A GENERAL MODEL A SPECI?C MODEL RESTRICTING THE PROTEIN LEVEL COST THE COST OF AN ALIGNMENT A SIMPLE ALIGNMENT ALGORITHM AN IMPROVED ALIGNMENT ALGORITHM REDUCING SPACE CONSUMPTION CONCLUSION MEASURES ON HIDDEN MARKOV MODELS CO-EMISSION PROBABILITY OF TWO MODELS OTHER TYPES OF HIDDEN MARKOV MODELS HIDDEN MARKOV MODELS WITH ONLY SIMPLE CYCLES GENERAL HIDDEN MARKOV MODELS EXPERIMENTS FINDING MAXIMAL PAIRS WITH BOUNDED GAP PRELIMINARIES PAIRS WITH UPPER AND LOWER BOUNDED GAP DATA STRUCTURES ALGORITHMS PAIRS WITH LOWER BOUNDED GAP FINDING MAXIMAL QUASIPERIODICITIES IN STRINGS DE?NITIONS MAXIMAL QUASIPERIODIC SUBSTRINGS SEARCHING AND MERGING HEIGHT-BALANCED TREES ALGORITHM RUNNING TIME ACHIEVING LINEAR SPACE PREDICTION OF RNA SECONDARY STRUCTURE BASIC DYNAMIC PROGRAMMING ALGORITHM E?CIENT EVALUATION OF INTERNAL LOOPS FINDING OPTIMAL INTERNAL LOOPS THE ASYMMETRY FUNCTION ASSUMPTION COMPUTING THE PARTITION FUNCTION IMPLEMENTATION A CONSTRUCTED “MEAN” SEQUENCE THERMOCOCCUS CELER 10 PROTEIN FOLDING IN THE 2D HP MODEL 10 1 INTRODUCTION 10 2 THE 2D HP MODEL 10 3 THE FOLDING ALGORITHMS 10 4 THE CIRCLE PROBLEM 10 4 1 UPPER BOUNDING THE C-FOLD APPROXIMATION RATIO 10 4 2 LOWER BOUNDING THE C-FOLD APPROXIMATION RATIO 10 5 CONCLUSION