Computational Systems Bioinformatics: Csb2007 Conference Proceedings, University of California, San Diego, USA, 13-17 August 2007

CONTENTS......Page 14
Preface......Page 8
Committees......Page 10
Referees......Page 12
Keynote Address......Page 18
Quantitative Aspects of Gene Regulation in Bacteria: Amplification. Threshold, and Combinatorial Control Terry Hwa......Page 20
Whole-Genome Analysis of Dorsal Gradient Thresholds in the Drosophila Embryo Julia ZeitlingeK Rob Zinzen, Dmitri Papatsenko et al.......Page 22
Invited Talks......Page 24
Learning Predictive Models of Gene Regulation Christina Leslie......Page 26
The Phylofacts Phylogenomic Encyclopedias: Structural Phylogenomic Analysis Across the Tree of Life Kimmen Golander......Page 28
1. INTRODUCTION......Page 30
Gene-Centered Protein-DNA lnteractome Mapping A.J. Marian Walhout......Page 32
Proteomics......Page 34
The anti-symmetric problem......Page 36
2.1. General Terminologies......Page 37
2.3. Problems Analysis......Page 38
3.1. Preprocessing to remove noisy peaks and introduce pseudo peaks......Page 41
3.3. Novel Peptide Sequencing Algorithm......Page 42
4.1. Experiment Settings......Page 43
4.2. Results......Page 44
References......Page 46
1. INTRODUCTION......Page 48
2.1. Library Diversity......Page 49
2.2. Metrics for Breakpoint Selection......Page 50
2.3. Dynamic Programming for Breakpoint Selection......Page 51
3. RESULTS A N D DISCUSSION......Page 53
References......Page 56
1. INTRODUCTION......Page 58
1.1. Comparison of the Proposed Approach with Related Works......Page 59
2.1. Problem Formulation......Page 60
2.2.1. Finding the MS spectrum match......Page 61
2.2.2. Finding the MS/MS spectrum match......Page 62
2.2.5. Peak finding in the presence of noise......Page 63
2.2.6. Addressing isotopic variation and neutral loss......Page 64
3.2. Summary of Results......Page 65
3.2.1. Analysis of the effect of varying threshold t on results......Page 66
4. CONCLUSIONS AND DISCUSSION......Page 67
References......Page 68
Biomedical Application......Page 70
1. INTRODUCTION......Page 72
1 .1. Nonnegative matrix factorization......Page 73
2. INPUT SPACE, SUBSPACE AND KERNEL CLUSTERING......Page 74
2.2. Kernel space clustering: conduct clustering in a high dimension space with kernel tricks......Page 75
3. PG-NMF SUBSPACE KERNEL HIERARCHICAL CLASS1 FlCATlON......Page 76
4. EXPERIMENTS......Page 78
4.1. Comparing classification results from kNN, sparse-NMF and support vector machines (SVM)......Page 80
5. CONCLUSIONS......Page 81
References......Page 82
1. INTRODUCTION......Page 84
2. FORMULATION OF THE MCTS PROBLEM......Page 86
3.2. A Greedy Algorithm for MCTS......Page 87
4. EXPERIMENTAL RESULTS......Page 88
4.2. Genome-wide Tagging......Page 89
5. CONCLUSION......Page 91
References......Page 92
1. INTRODUCTION......Page 96
3.2. Transcription factor identification......Page 97
3.3. Transcriptional regulation in the different phases of DE formation......Page 98
References......Page 99
Pathways, Networks and Systems Biology......Page 100
1. INTRODUCTION......Page 102
2.1. Biological prior knowledge......Page 103
2.2. MCMC sampling scheme......Page 104
3.1. Cytometry data......Page 105
3.3. Biological prior knowledge......Page 106
5. RESULTS AND DISCUSSION......Page 107
References......Page 111
1 INTRODUCTION......Page 114
2 INTRODUCTION OF INDIRECT NEIGHBORS......Page 115
3 PCP ALGORITHM......Page 116
4 EXPERIMENTS......Page 117
References......Page 125
1. INTRODUCTION......Page 128
2.1. Motif Representation......Page 130
2.2.2. p-score......Page 131
3.1. Exact Algorithm......Page 132
3.2. Heuristics Algorithm......Page 133
4.1. SH3 Domains Dataset......Page 134
4.4. Simulated Data......Page 135
References......Page 136
1. INTRODUCTION......Page 138
2. STOCHASTIC BIOCHEMICAL SYSTEM ANALYSIS......Page 139
3.2. Computing the state transition probabilities and times......Page 140
3.2.2. Bimolecular reactions......Page 141
3.4. Computing the total probability of reaching a final state......Page 142
3.5. Computing the MFPT for reaching the final state......Page 143
3.6. Approximating the Markov Chain: Reducing complexity at the cost of accuracy......Page 144
4.1. Enzyme-Kinetics system......Page 145
4.2. Transcriptional Regulatory System......Page 147
6. CONCLUSION AND FUTURE DIRECTIONS......Page 148
References......Page 149
1. INTRODUCTION......Page 150
1.1.1. Incremental Association Markov Blanket......Page 152
1.2. Bayesian Networks......Page 153
2.2. Markov Blanket Inference......Page 154
2.3. Gene regulatory network reconstruction......Page 155
3.1. Simulations......Page 156
4. DISCUSSION......Page 157
References......Page 159
1. INTRODUCTION......Page 162
3. PROBLEM SETUP......Page 163
4. DTI FORMULATION......Page 164
6. KERNEL DENSITY ESTIMATION (KDE)......Page 166
8. SUMMARY OF ALGORITHM......Page 167
9.2. Directed Network inference: Gata3 Regulation in Early Kidney Development......Page 169
9.4. Phylogenetic conservation of TFBS effectors......Page 170
References......Page 172
1. INTRODUCTION......Page 174
2. RELATED WORKS......Page 175
3.1. Mining for dense subgraphs......Page 176
3.1.1. Mining for local dense subgraphs......Page 177
3.2.1. Computing reliability of protein interactions......Page 178
4. EXPERIMENTS......Page 180
4.2. Comparative results......Page 181
4.4. Effect of parameters w and y......Page 182
4.5. Analysis of the predicted complexes......Page 183
5. Conclusions......Page 184
References......Page 185
1. INTRODUCTION......Page 186
2.2. Consistency statistics : interference and crosstalk......Page 187
2.3. Interrogating contexts via in-silico conditioning......Page 188
3. EVALUATION OF THE ALGORITHM......Page 189
4.1. Analysis of melanoma gene expression profile......Page 191
4.2.2. Patterns of drug-gene interactions......Page 192
5. CONCLUSION......Page 194
References......Page 195
Genomics......Page 198
1. INTRODUCTION......Page 200
2.1. AMOSA......Page 201
2.2. Data......Page 202
2.5. Prediction System......Page 203
2.7. Other TSS Prediction Methods......Page 205
3.3. Comparison with Other Methods......Page 206
References......Page 209
1. INTRODUCTION......Page 212
2.1. Main ortholog clusters for three genomes......Page 213
3.1. Validation using gene annotation......Page 215
3.3. Comparison with MultiParanoid......Page 216
References......Page 217
1. INTRODUCTION......Page 220
2.2. Basic Deconvolution......Page 222
2.3. Deconvolution Using an Imperfect Physical Map......Page 223
2.3.2. Relaxation and randomized rounding......Page 224
2.4. Deconvolution Using a Perfect Physical Map......Page 225
2.4.2. Relaxation, rounding and analysis......Page 226
3.2. Experimental Results on the Rice Genome......Page 227
3.3. Experimental Results on the Barley Genome......Page 229
References......Page 230
1. INTRODUCTION......Page 232
2. PROBLEM DESCRIPTION AND METHODOLOGY......Page 233
2.2. Scoring a Grammar......Page 235
2.3. Optimization Through Nesting Grammars......Page 236
2.5. Integrating Relationships in Data into Search......Page 237
3. ALGORITHM......Page 238
4. RESULTS......Page 239
ACKNOWLEDGMENTS......Page 241
References......Page 242
1. INTRODUCTION......Page 244
2.1.3. /EM Alaorithm......Page 246
2.2. Evaluation Approaches......Page 247
3.1.1. Arginine pathway data s e t......Page 248
3.2. Results on AmpR......Page 249
3.3. Results on Whole Genomic Data......Page 250
REFERENCES......Page 251
1. Introduction......Page 254
2.2. Stage one: constructing profile template......Page 256
2.3.1. Vote among hits......Page 257
2.3.2. Bind hits greedily......Page 258
2.4. Stage three: iterative refinement......Page 259
3.4. The assessment......Page 260
4. Discussion......Page 261
References......Page 262
1. INTRODUCTION......Page 266
2.1. Learning PWMs from sequences......Page 268
2.2. Learning PWMs from both sequences and expression......Page 269
2.4. Performance evaluation of putative motifs......Page 270
3.1. Simulated data......Page 271
3.2. Real data......Page 272
3.2.2. ChlP-chip data......Page 273
References......Page 276
Structural Bioinformatics......Page 278
1. INTRODUCTION......Page 280
2.2. Recognition of binding sites......Page 281
3.2. Characterizing cavities in terms of blocked points......Page 282
4.1. Cavity detection......Page 283
4.2. Finding similar binding sites on two proteins......Page 284
5.1. Cavity detection......Page 285
5.2. Finding similar binding sites o n two proteins......Page 288
6. CONCLUSIONS......Page 290
REFERENCES......Page 291
1. INTRODUCTION......Page 292
2. BACKGROUND AND RELATED WORK......Page 293
3.1. Pocket Extraction......Page 294
3.2. Signed Distance Functions......Page 296
3.3. Quantitative Analysis and Visualization......Page 298
4. IMPLEMENTATION AND EXAMPLES......Page 300
References......Page 301
1. INTRODUCTION......Page 304
2. RELATED WORKS......Page 305
3. DATA REPRESENTATION......Page 306
4.2. Feature Vector Generation......Page 307
4.3. Clustering......Page 308
5.1. Visual Verification......Page 309
5.2. Structural Diversity of Interfaces’ Parent Chains......Page 310
5.3. Occurrences of Important Biological Motifs......Page 311
6. CONCLUSIONS......Page 313
References......Page 314
1. INTRODUCTION......Page 316
2.2. Our Results......Page 317
3. METHOD......Page 318
3.2. Initial POG Construction......Page 319
3.2.2. Scoring Function......Page 320
3.3. Merging Stage......Page 322
4.3. Investigation on Entire Protein Structure......Page 323
4.4.1. Alpha-Helix Substructure......Page 324
4.5. Timing of EPO......Page 325
References......Page 326
1. INTRODUCTION......Page 328
3. PROBLEM STATEMENT......Page 329
4.1.1 - Profile Information......Page 330
4.3. Kernel Functions......Page 331
5.4. Evaluation Methodology......Page 332
6. RESULTS......Page 333
6.3. Input Information and Coding Schemes......Page 334
6.4.1. Reliability Prediction Problem......Page 335
6.4.2. fWsD Estimation Problem......Page 336
ACKNOWLEDGEMENTS......Page 337
References......Page 338
1.1. Related Work......Page 340
1.2. Our Contributions......Page 341
3.1. Maximum Likelihood Estimation of Server Correlations......Page 342
3.3. ILP Model to Weigh Latent Servers......Page 343
4.1. Data Set......Page 344
4.2. Server Correlations and Latent Servers......Page 345
4.3. CASP7 Evaluation......Page 346
5. DISCUSSIONS......Page 348
References......Page 349
1. INTRODUCTION......Page 352
2. METHODS......Page 353
3. RESULTS......Page 355
References......Page 358
1. INTRODUCTION......Page 360
2.1. Related Work in Motif Design......Page 361
2.2. Earlier Motif Matching Algorithms......Page 362
3.2. Composite Motifs......Page 363
3.2.3. Advantages of Composite Motifs......Page 364
4.1. Protein Families......Page 365
4.2. Motifs used in Experimentation......Page 367
4.5. Averaged and Centered Motifs are Sensitive and Specific......Page 368
ACKNOWLEDGEMENTS......Page 370
References......Page 371
Ontology, Database and Text Mining......Page 374
1. INTRODUCTION......Page 376
2.2. PubViz Web Services......Page 379
2.4. High Performance Similarity Calculation and Clustering Using 8800GTX......Page 380
3.1. PubViz User Interface......Page 381
3.3. Data Visualization......Page 382
4. DISCUSSION......Page 384
References......Page 385
1. BACKGROUND......Page 388
2.1. Identification of Gene Mentions......Page 389
2.2.1. Coverage......Page 390
2.2.4. Discrete Features......Page 391
3. EVALUATION......Page 392
4. DISCUSSION......Page 393
References......Page 396
1. INTRODUCTION......Page 398
2.1. Usage......Page 399
3. RESULTS AND DISCUSSION......Page 400
References......Page 401
Biocomputing......Page 402
2. MATERIALS AND METHODS......Page 404
3.2. Clustering Algorithms......Page 405
References......Page 407
1. INTRODUCTION......Page 408
2. FIXED-PARAMETER ALGORITHM......Page 410
3. GREEDY HEURISTIC......Page 411
4. LAYOUT-BASED HEURISTIC......Page 413
5 . RESULTS......Page 414
6. DISCUSSION AND CONCLUSION......Page 416
References......Page 417
1. INTRODUCTION......Page 420
3. DEFINITIONS AND NOTATIONS......Page 421
5. METHODS......Page 422
5.1.3. Sum-based Search......Page 423
5.2. Nearest-Neighbor Graph-based Methods......Page 424
7.1. Datasets......Page 425
7.4. Standard Retrieval......Page 426
8.1.1. Performance of Relevance Feedback Methods......Page 427
CONCLUSION......Page 428
ACKNOWLEDGEMENTS......Page 429
References......Page 430
Transcriptomics and Phylogeny......Page 432
1. INTRODUCTION......Page 434
2. THE MICROARRAY LAYOUT PROBLEM......Page 435
3. ANALYSIS OF GENECHIP ARRAYS......Page 437
4.1. Review of Existing Placement and Re- Embedding Strategies......Page 439
4.2. Greedy+: Merging Placement and Embedding......Page 441
4.3. Results on Chips with Random Probes......Page 442
References......Page 443
1. INTRODUCTION......Page 446
2. MODEL OF SPECIES-GENES DATA......Page 447
4. ALGORITHM OF ESTIMATING SAPROBABILlTY DISTRlBUTI0NS: GENERALEZED REPLICAT0R DYNAMICS......Page 450
4.1. Replicator Dynamics......Page 451
4.2. Generalized Replicator Dynamics......Page 452
5 . EMPIRICAL STUDY......Page 453
6. CONCLUSIONS AND FUTURE WORKS......Page 455
References......Page 456
1. INTRODUCTION......Page 458
2. NOTATION AND BINARY RECONCILIATION......Page 459
3. MODELS FOR NON-BINARY SPECIES TREES......Page 460
4. IDENTIFYING DUPLICATIONS......Page 461
5. IDENTIFYING LOSS NODES......Page 463
5.1. Minimizing Explicit Losses......Page 464
5.2. Minimizing Combined Losses......Page 465
6. EMPIRICAL RESULTS......Page 467
References......Page 468
Author Index......Page 470