Regulatory Genomics: Proceedings of the 3rd Annual RECOMB Workshop, National University of Singapore, Singapore 17-18 July 2006 (Series on Advances in Bioinformatics and Computational Biology)

Research in the field of gene regulation is evolving rapidly in the ever-changing scientific environment. Advances in microarray techniques and comparative genomics have enabled more comprehensive studies of regulatory genomics. The study of genomic binding locations of transcription factors has enabled a more comprehensive modeling of regulatory networks. In addition, complete genomic sequences and comparison of numerous related species have demonstrated the conservation of non-coding DNA sequences, which often provide evidence for cis-regulatory binding sites. Systematic methods to decipher the regulatory mechanism are also crucial for corroborating these regulatory networks; key to these methods are motif discovery algorithms that can help predict cis-regulatory elements. These DNA-motif discovery programs are becoming more sophisticated and are beginning to leverage evidence from comparative genomics. These topics and more were discussed at the 3rd Annual RECOMB Workshop on Regulatory Genomics, which brought together more than 90 attendees and included about 22 excellent talks from leading researchers in the field. This proceedings volume contains ten selected, original manuscripts that were presented during the workshop. CONTENTS 10 Foreword 6 RECOMB Regulatory Genomics 2006 Organization 8 Keynote Papers 14 Computational Prediction of Regulatory Elements by Comparative Sequence Analysis M. Tompa 16 A Tale of Two Topics - Motif Significance and Sensitivity of Spaced Seeds M. Li 17 Computational Challenges for Top-Down Modeling and Simulation of Biological Pathways S. Miyano 18 An Improved Gibbs Sampling Method for Motif Discovery via Sequence Weighting T. Jiang 19 Discovering Motifs with Transcription Factor Domain Knowledge F. Chin 20 Applications of ILP in Computational Biology A . Dress 21 On the Evolution of Transcription Regulation Networks R. Shamir 22 Systems Pharmacology in Cancer Therapeutics: Iterative Informatics-Experimental Interface E. Liu 23 Computational Structural Proteomics and Inhibitor Discovery R. Abagyan 24 Characterization of Transcriptional Responses to Environmental Stress by Differential Location Analysis H. Tang 25 A Knowledge-based Hybrid Algorithm for Protein Secondary Structure Prediction W. L. Hsu 26 Monotony and Surprise (Conservative Approaches to Pattern Discovery) A . Apostolic0 27 Evolution of Bacterial Regulatory Systems M. S. Gelfand 28 Contributed Papers 30 TScan: A Two-step De NOVO Motif Discovery Method 0. Abul, G. K. Sandve, and F. Drabbs 32 1. Introduction 32 2. Method 34 2.1. Step1 35 2.2. Step2 36 2.2.1, Over-representutiordConservution Scoring 36 2.2.2. Frith et al. Scoring 37 3. Experiments 38 4. Conclusion 41 References 42 Redundancy Elimination in Motif Discovery Algorithms H. Leung and F. Chin 44 1. Introduction 44 2. Maximizing Likelihood 47 3. The Motif Redundancy Problem 48 3.1. The motif redundancy problem 48 3.2. Formal definition 48 4. Algorithm 49 5. Experimental Results 50 6. Concluding Remarks 52 Appendix 52 References 53 GAMOT: An Efficient Genetic Algorithm for Finding Challenging Motifs in DNA Sequences N. Karaoglu, S. Maurer-Stroh, and B. Manderick 56 1. Introduction 56 2. GA for Motif Finding 58 3. An Efficient Algorithm (GAMOT) 58 3.1. Fast motif discovery 58 3.2. The genetic algorithm 60 4. Experimental Results 61 4.1. Comparison with exhaustive search 62 4.2. Comparison with GAI and GA2 62 4.3. Comparison with other algorithms 62 4.3.1. Quality ofthe solutions 63 4.4. GAMOTparameters 63 5. Conclusions and Future Work 65 References 66 Identification of Spaced Regulatory Sites via Submotif Modeling E. Wijaya and R. Kanagasabai 70 1. Introduction 70 2. Related Work 71 3. Our Approach 71 4. Problem Definition 72 5. Algorithm SPACE 73 5.1. Generation of candidate motifs 74 5.2. Constrained frequent pattern mining 74 5.2.1. Generalized gap 75 5.2.2. Mining of constrained frequent patterns 75 5.3. Significance testing and scoring 79 6. Experimental Results 80 6.1. Results on Tompa’s benchmark data set 80 6.2. Results on synthetic data set 83 7. Discussion and Conclusions 83 References 84 Refining Motif Finders with E-value Calculations N. Nagarajan, P. Ng, and U. Keich 86 1. Introduction 86 2. Efficiently Computing E-values 88 3. Optimizing for E-values - Conspv 90 4. E-value Based Improvements of the Gibbs Sampler 91 5 . Conclusion 94 6. Methods 94 Acknowledgements 96 References 96 Multiple Indexing Sequence Alignment for Group Feature Identification W.-Y. Chou, T.-W. Pai, J. Z.-C. Lai, W.-S. Tzou, M, D.-T. Chang, H.-T. Chang, W.-Y. Chou, and T.-C. Fan 98 1. Introduction 98 2. Preliminaries 99 3. System Architecture 100 3.1. Interval jumping searching algorithm 101 3.2. Hierarchical clustering technique 101 3.3. Multiple indexing sequence alignment 102 3.4. Group feature identification 102 4. Experimental Results 103 4.1. Comparison with existing algorithms for combinatorial patterns 103 4.2, Transcription elements prediction 106 4.3. Exclusive group feature identification 107 5. Conclusions 109 References 110 Improving the Accuracy of Signal Transduction Pathway Construction Using Level-2 Neighbours T. K. F. Wong, S. M. Yiu, T. W. Lam, and S. C. K. Wong 112 1. Introduction 112 2. The Problem 115 3. Our Approach 116 3.1. The scoring function 116 3.2. The randomized algorithm 117 3.3. Cleansing of gene expression data 118 4. Experiments 118 5. Conclusion 120 References 120 Investigating Roles of DNA Flexibility in Promoter Recognition and Regulation J. D. Bashford 122 1. Introduction 122 2. Materials and Methods 123 2.1. Promoter sequences 123 2.2. DNA flexibility model 124 2.3. Flexibility parameters 126 3. Results 127 3.1. T7 Promoter sequences are associated with high flexibility 127 3.2. Effects of varying L, 8 128 3.3. Promoter comparison 130 4. Discussion 132 Acknowledgments 133 References 133 Regulatory Networks of Genes Affected By MorA, A Global Regulator Containing GGDEF and EAL Domains in Pseudomonas Aeruginosa W.-K. Choy, V. B. Bajic, M.- W. Heng, M. Veronika, and S. Swamp 136 1. Introduction 137 2. Methods and Discussion 138 3. Conclusion 142 Acknowledgments 142 References 142 Author Index 144 CONTENTS......Page 10 Foreword......Page 6 RECOMB Regulatory Genomics 2006 Organization......Page 8 Keynote Papers......Page 14 Computational Prediction of Regulatory Elements by Comparative Sequence Analysis M. Tompa......Page 16 A Tale of Two Topics - Motif Significance and Sensitivity of Spaced Seeds M. Li......Page 17 Computational Challenges for Top-Down Modeling and Simulation of Biological Pathways S. Miyano......Page 18 An Improved Gibbs Sampling Method for Motif Discovery via Sequence Weighting T. Jiang......Page 19 Discovering Motifs with Transcription Factor Domain Knowledge F. Chin......Page 20 Applications of ILP in Computational Biology A . Dress......Page 21 On the Evolution of Transcription Regulation Networks R. Shamir......Page 22 Systems Pharmacology in Cancer Therapeutics: Iterative Informatics-Experimental Interface E. Liu......Page 23 Computational Structural Proteomics and Inhibitor Discovery R. Abagyan......Page 24 Characterization of Transcriptional Responses to Environmental Stress by Differential Location Analysis H. Tang......Page 25 A Knowledge-based Hybrid Algorithm for Protein Secondary Structure Prediction W. L. Hsu......Page 26 Monotony and Surprise (Conservative Approaches to Pattern Discovery) A . Apostolic0......Page 27 Evolution of Bacterial Regulatory Systems M. S. Gelfand......Page 28 Contributed Papers......Page 30 1. Introduction......Page 32 2. Method......Page 34 2.1. Step1......Page 35 2.2.1, Over-representutiordConservution Scoring......Page 36 2.2.2. Frith et al. Scoring......Page 37 3. Experiments......Page 38 4. Conclusion......Page 41 References......Page 42 1. Introduction......Page 44 2. Maximizing Likelihood......Page 47 3.2. Formal definition......Page 48 4. Algorithm......Page 49 5. Experimental Results......Page 50 Appendix......Page 52 References......Page 53 1. Introduction......Page 56 3.1. Fast motif discovery......Page 58 3.2. The genetic algorithm......Page 60 4. Experimental Results......Page 61 4.3. Comparison with other algorithms......Page 62 4.4. GAMOTparameters......Page 63 5. Conclusions and Future Work......Page 65 References......Page 66 1. Introduction......Page 70 3. Our Approach......Page 71 4. Problem Definition......Page 72 5. Algorithm SPACE......Page 73 5.2. Constrained frequent pattern mining......Page 74 5.2.2. Mining of constrained frequent patterns......Page 75 5.3. Significance testing and scoring......Page 79 6.1. Results on Tompa’s benchmark data set......Page 80 7. Discussion and Conclusions......Page 83 References......Page 84 1. Introduction......Page 86 2. Efficiently Computing E-values......Page 88 3. Optimizing for E-values - Conspv......Page 90 4. E-value Based Improvements of the Gibbs Sampler......Page 91 6. Methods......Page 94 References......Page 96 1. Introduction......Page 98 2. Preliminaries......Page 99 3. System Architecture......Page 100 3.2. Hierarchical clustering technique......Page 101 3.4. Group feature identification......Page 102 4.1. Comparison with existing algorithms for combinatorial patterns......Page 103 4.2, Transcription elements prediction......Page 106 4.3. Exclusive group feature identification......Page 107 5. Conclusions......Page 109 References......Page 110 1. Introduction......Page 112 2. The Problem......Page 115 3.1. The scoring function......Page 116 3.2. The randomized algorithm......Page 117 4. Experiments......Page 118 References......Page 120 1. Introduction......Page 122 2.1. Promoter sequences......Page 123 2.2. DNA flexibility model......Page 124 2.3. Flexibility parameters......Page 126 3.1. T7 Promoter sequences are associated with high flexibility......Page 127 3.2. Effects of varying L, 8......Page 128 3.3. Promoter comparison......Page 130 4. Discussion......Page 132 References......Page 133 Regulatory Networks of Genes Affected By MorA, A Global Regulator Containing GGDEF and EAL Domains in Pseudomonas Aeruginosa W.-K. Choy, V. B. Bajic, M.- W. Heng, M. Veronika, and S. Swamp......Page 136 1. Introduction......Page 137 2. Methods and Discussion......Page 138 References......Page 142 Author Index......Page 144