Algorithms in Bioinformatics

Paul A. Gagniuc, PhD, is an associated Professor of Bioinformatics and a Professor of Programming Languages at University Politehnica of Bucharest in Romania. He obtained his doctorate in Genetics at the University of Bucharest. Dr. Gagniuc is also an Academic Editor at PLoS ONE and a pro-active reviewer for several well-known scientific journals. He has published numerous high-profile scientific articles and is the recipient of several awards for exceptional scientific results.

• Preface   xvAbout the Companion Website xvii1              The Tree of Life (I)  11.1          Introduction 11.2          Emergence of Life 11.2.1      Timeline Disagreements 31.3          Classifications and Mechanisms 41.4          Chromatin Structure 51.5          Molecular Mechanisms 91.5.1      Precursor Messenger RNA 91.5.2      Precursor Messenger RNA to Messenger RNA 101.5.3      Classes of Introns 101.5.4      Messenger RNA 101.5.5      mRNA to Proteins 111.5.6      Transfer RNA 121.5.7      Small RNA 121.5.8      The Transcriptome 131.5.9      Gene Networks and Information Processing 131.5.10    Eukaryotic vs. Prokaryotic Regulation 141.5.11    What Is Life? 141.6          Known Species 141.7          Approaches for Compartmentalization 151.7.1      Two Main Approaches for Organism Formation 161.7.2      Size and Metabolism 161.8          Sizes in Eukaryotes 161.8.1      Sizes in Unicellular Eukaryotes 171.8.2      Sizes in Multicellular Eukaryotes 171.9          Sizes in Prokaryotes 171.10        Virus Sizes 181.10.1    Viruses vs. the Spark of Metabolism 201.11        The Diffusion Coefficient 201.12        The Origins of Eukaryotic Cells 211.12.1    Endosymbiosis Theory 211.12.2    DNA and Organelles 221.12.3    Membrane-bound Organelles with DNA 231.12.4    Membrane-bound Organelles Without DNA 231.12.5    Control and Division of Organelles 241.12.6    The Horizontal Gene Transfer 241.12.7    On the Mechanisms of Horizontal Gene Transfer 251.13        Origins of Eukaryotic Multicellularity 261.13.1    Colonies Inside an Early Unicellular Common Ancestor 261.13.2    Colonies of Early Unicellular Common Ancestors 261.13.3    Colonies of Inseparable Early Unicellular Common Ancestors1.13.4    Chimerism and Mosaicism 281.14        Conclusions 292              Tree of Life: Genomes (II)   312.1          Introduction 312.2          Rules of Engagement 312.3          Genome Sizes in the Tree of Life 322.3.1      Alternative Methods 332.3.2      The Weaving of Scales 332.3.3      Computations on the Average Genome Size 362.3.4      Observations on Data 382.4          Organellar Genomes 402.4.1      Chloroplasts 402.4.2      Apicoplasts 402.4.3      Chromatophores 422.4.4      Cyanelles 422.4.5      Kinetoplasts 422.4.6      Mitochondria 432.5          Plasmids 432.6          Virus Genomes 442.7          Viroids and Their Implications 462.8          Genes vs. Proteins in the Tree of Life 472.9          Conclusions 493              Sequence Alignment (I)   513.1          Introduction 513.2          Style and Visualization 513.3          Initialization of the Score Matrix 543.4          Calculation of Scores 573.4.1      Initialization of the Score Matrix for Global Alignment 573.4.2      Initialization of the Score Matrix for Local Alignment 623.4.3      Optimization of the Initialization Steps 653.4.4      Curiosities 663.5          Traceback   713.6          Global Alignment 753.7          Local Alignment 793.8          Alignment Layout 843.9          Local Sequence Alignment – The Final Version 873.10        Complementarity 913.11        Conclusions 974              Forced Alignment (II)   994.1          Introduction 994.2          Global and Local Sequence Alignment 1004.2.1      Short Notes 1004.2.2      Understanding the Technology 1014.2.3      Main Objectives 1024.3          Experiments and Discussions 1024.3.1      Alignment Layout 1064.3.2      Forced Alignment Regime 1064.3.3      Alignment Scores and Significance 1094.3.4      Optimal Alignments 1104.3.5      The Main Significance Scores 1104.3.6      The Information Content 1104.3.7      The Match Percentage 1124.3.8      Significance vs. Chance 1134.3.9      The Importance of Randomness 1134.3.10    Sequence Quality and the Score Matrix 1144.3.11    The Significance Threshold 1154.3.12    Optimal Alignments by Numbers 1164.3.13    Chaos Theory on Sequence Alignment 1164.3.14    Image-Encoding Possibilities 1164.4          Advanced Features and Methods 1174.4.1      Sequence Detector 1174.4.2      Parameters 1174.4.3      Heatmap 1184.4.4      Text Visualization 1234.4.5      Graphics for Manuscript Figures and Didactic Presentations 1244.4.6      Dynamics 1244.4.7      Independence 1254.4.8      Limits 1254.4.9      Local Storage 1254.5          Conclusions 1285              Self-Sequence Alignment (I)  1295.1          Introduction 1295.2          True Randomness 1305.3          Information and Compression Algorithms 1305.4          White Noise and Biological Sequences 1315.5          The Mathematical Model 1315.5.1      A Concrete Example 1325.5.2      Model Dissection 1335.5.3      Conditions for Maxima and Minima 1365.6          Noise vs. Redundancy 1375.7          Global and Local Information Content 1375.8          Signal Sensitivity 1385.9          Implementation 1405.9.1      Global Self-Sequence Alignment 1405.9.2      Local Self-Sequence Alignment 1445.10        A Complete Scanner for Information Content 1475.11        Conclusions 1496              Frequencies and Percentages (II)   1516.1          Introduction 1516.2          Base Composition 1526.3          Percentage of Nucleotide Combinations 1526.4          Implementation 1536.5          A Frequency Scanner 1566.6          Examples of Known Significance 1586.7          Observation vs. Expectation 1606.8          A Frequency Scanner with a Threshold 1616.9          Conclusions 1637              Objective Digital Stains (III)  1657.1          Introduction 1657.2          Information and Frequency 1667.3          The Objective Digital Stain 1697.3.1      A 3D Representation Over a 2D Plane 1737.3.2      ODSs Relative to the Background 1777.4          Interpretation of ODSs 1817.5          The Significance of the Areas in the ODS 1837.6          Discussions 1847.6.1      A Similarity Between Dissimilar Sequences 1867.7          Conclusions 1868              Detection of Motifs (I)   1878.1          Introduction 1878.2          DNA Motifs 1878.2.1      DNA-binding Proteins vs. Motifs and Degeneracy 1888.2.2      Concrete Examples of DNA Motifs 1888.3          Major Functions of DNA Motifs 1918.3.1      RNA Splicing and DNA Motifs 1918.4          Conclusions 1959              Representation of Motifs (II)   1979.1          Introduction 1979.2          The Training Data 1979.3          A Visualization Function 1989.4          The Alignment Matrix 2009.5          Alphabet Detection 2039.6          The Position-Specific Scoring Matrix (PSSM) Initialization 2069.7          The Position Frequency Matrix (PFM)  2079.8          The Position Probability Matrix (PPM)  2089.8.1      A Kind of PPM Pseudo-Scanner 2099.9          The Position Weight Matrix (PWM) 2129.10        The Background Model 2159.11        The Consensus Sequence 2189.11.1    The Consensus – Not Necessarily Functional 2199.12        Mutational Intolerance 2219.13        From Motifs to PWMs 2229.14        Pseudo-Counts and Negative Infinity 2269.15        Conclusions 22910           The Motif Scanner (III)   23110.1        Introduction 23110.2        Looking for Signals 23210.3        A Functional Scanner 23510.4        The Meaning of Scores 23910.4.1    A Score Value Above Zero 23910.4.2    A Score Value Below Zero  24110.4.3    A Score Value of Zero 24110.5        Conclusions 24211           Understanding the Parameters (IV)   24311.1        Introduction 24311.2        Experimentation 24311.2.1    A Scanner Implementation Based on Pseudo-Counts 24411.2.2    A Scanner Implementation Based on Propagation of Zero Counts 24611.3        Signal Discrimination 24911.4        False-Positive Results 25011.5        Sensitivity Adjustments 25111.6        Beyond Bioinformatics 25211.7        A Scanner That Uses a Known PWM 25311.8        Signal Thresholds 25611.8.1    Implementation and Filter Testing 25811.9        Conclusions 26212           Dynamic Backgrounds (V)   26312.1        Introduction 26312.2        Toward a Scanner with Two PFMs 26312.2.1    The Implementation of Dynamic PWMs 26412.2.2    Issues and Corrections for Dynamic PWMs 27112.2.3    Solutions for Aberrant Positive Likelihood Values 27412.3        A Scanner with Two PFMs 28012.4        Information and Background Frequencies on Score Values 28312.5        Dynamic Background vs. Null Model 28512.6        Conclusions 28513           Markov Chains: The Machine (I)   28713.1        Introduction 28713.2        Transition Matrices 28713.3        Discrete Probability Detector 29213.3.1    Alphabet Detection 29213.3.2    Matrix Initialization  29313.3.3    Frequency Detection  29513.3.4    Calculation of Transition Probabilities 29713.3.5    Particularities in Calculating the Transition Probabilities 30613.4        Markov Chains Generators 30713.4.1    The Experiment 30813.4.2    The Implementation 31213.4.3    Simulation of Transition Probabilities 31513.4.4    The Markov machine  31513.4.5    Result Verification  31713.5        Conclusions 31814           Markov Chains: Log Likelihood (II)  31914.1        Introduction 31914.2        The Log-Likelihood Matrix 31914.2.1    A Log-Likelihood Matrix Based on the Null Model 32014.2.2    A Log-Likelihood Matrix Based on Two Models 32214.3        Interpretation and Use of the Log-Likelihood Matrix  32614.4        Construction of a Markov Scanner 32814.5        A Scanner That Uses a Known LLM 33714.6        The Meaning of Scores 34014.7        Beyond Bioinformatics 34414.8        Conclusions 34515           Spectral Forecast (I)   34715.1        Introduction 34715.2        The Spectral Forecast Model 34715.3        The Spectral Forecast Equation 34915.4        The Spectral Forecast Inner Workings 35015.4.1    Each Part on a Single Matrix  35115.4.2    Both Parts on a Single Matrix  35215.4.3    Both Parts on Separate Matrices 35315.4.4    Concrete Example 1  35415.4.5    Concrete Example 2  35715.4.6    Concrete Example 3  35915.5        Implementations 36015.5.1    Spectral Forecast for Signals 36215.5.2    What Does the Value of d Mean? 36415.5.3    Spectral Forecast for Matrices 36815.6        The Spectral Forecast Model for Predictions 37215.6.1    The Spectral Forecast Model for Signals 37215.6.2    Experiments on the Similarity Index Values 38115.6.3    The Spectral Forecast Model for Matrices 38415.7        Conclusions 38916           Entropy vs. Content (I)   39116.1        Introduction 39116.2        Information Entropy 39116.3        Implementation 39516.4        Information Content vs. Information Entropy 40016.4.1    Implementation 40316.4.2    Additional Considerations 40916.5        Conclusions 40917           Philosophical Transactions    41117.1        Introduction 41117.2        The Frame of Reference 41117.2.1    The Fundamental Layer of Complexity 41217.2.2    On the Complexity of Life 41417.3        Random vs. Pseudo-random 41517.4        Random Numbers and Noise 41817.5        Determinism and Chaos 41917.5.1    Chaos Without Noise 42017.5.2    Chaos with Noise 42717.5.3    Limits of Prediction 43017.5.4    On the Wings of Chaos 43117.6        Free Will and Determinism 43117.6.1    The Greatest Disappointment 43217.6.2    The Most Powerful Processor in Existence 43317.6.3    Certainty vs. Interpretation 43517.6.4    A Wisdom that Applies 43617.7        Conclusions 439Appendix A         441A.1         Association of Numerical Values with Letters 441A.2         Sorting Values on Columns 443A.3         The Implementation of a Sequence Logo 446A.4         Sequence Logos Based on Maximum Values 451A.5         Using Logarithms to Build Sequence Logos 455A.6         From a Motif Set to a Sequence Logo 459References   467Index   489