Proceedings of the 6th Asia-Pacific Bioinformatics Conference: Kyoto, Japan, 14-17 January 2008 (Series on Advances in Bioinformatics and Computational Biology)

Contributed Papers......Page 12
Preface......Page 6
APBC 2008 Organization......Page 8
Program Committee......Page 9
Additional Reviewers......Page 11
1. Background......Page 18
References......Page 19
KEGG for Medical and Pharmaceutical Applications Minoru Kanehisa......Page 22
Protein Interactions Extracted from Genomes and Papers Alfonso Valencia......Page 24
1. Introduction......Page 26
2.2. Pramework definition......Page 27
2.3. Relations with existing string kernels......Page 28
3.2. Leaf traversal algorithm......Page 29
4. Selecting feature groups and weights......Page 30
4.2. Statistically selecting feature groups......Page 31
5. Experiment......Page 32
6. Discussion and future work......Page 34
References......Page 35
1. Introduction......Page 36
2. Background......Page 37
3.2. Model......Page 38
4. Results......Page 40
5 . Conclusion......Page 42
References......Page 45
1. Introduction......Page 46
2.2. Sorting Signals......Page 47
3. Ensemble Methods......Page 48
3.2. Selection of Base Methods for Ensembles......Page 49
3.3. Ensemble Method Based on a Voting Schema......Page 50
3.4. Ensemble Method Based on Decision Trees......Page 51
4. Evaluation......Page 52
5. Conclusions......Page 53
References......Page 54
1. Introduction......Page 56
2.1. Marginalized and Optimal Assignment Graph Kernels......Page 57
3. Background......Page 58
4.2. Optimal Assignment Kernel......Page 59
4.3. Reduced Graph Representation......Page 60
5.1. Data Sets......Page 61
5.2. Methods......Page 62
5.3. Results......Page 63
6. Conclusions......Page 64
References......Page 65
1. Introduction......Page 66
2.2. Snake structures......Page 69
3.1. Saturated folds......Page 70
3.2. 2DHPSolver: a semi-automatic prover......Page 71
4. Stability of the snake structures......Page 72
References......Page 75
1 Introduction......Page 76
2 Methods......Page 77
3 Background and Related Works......Page 78
5 Results......Page 80
6 Conclusion and Discussion......Page 82
References......Page 83
1. Introduction......Page 86
2. AAPAZRS: Our algorithm to discover 3D pattern pairs......Page 87
2.2. Mpair (step one): Discovering maximal quasi-bidique subgraphs from transient and obligate complexes......Page 88
3. Results......Page 89
3.1. Amino acid dishibutions on each side of 3Dpattern pairs......Page 90
4. Discussion......Page 93
References......Page 95
1. Introduction......Page 96
2.1. Structural descriptors of protein-protein binding sites......Page 98
2.3. Structural descriptors of protein surface patches......Page 100
3.1. Retrieving SimilQr Binding Sites - Kinases......Page 101
4. Conclusion and Outlook......Page 103
References......Page 104
1. Introduction......Page 106
3.1. Structural alignment......Page 108
3.2. Structural alignment for simple pseudoknot......Page 109
3.3. Our memory-efficient algorithm......Page 110
3.4 Structural alignment for embedded simple pseudoknot......Page 113
5. Discussion and Conclusions......Page 115
References......Page 116
1. Introduction......Page 118
2.2. Block-level alignment......Page 119
2.3. Nucleotide-level alignment......Page 121
2.4. Computational complexity......Page 122
3.2. Comparison of computational time and memory......Page 123
4. Discussion......Page 125
References......Page 126
1. Introduction......Page 128
2. Definitions and Notations......Page 129
3.3. Projile Generation......Page 130
3.6. Gap Modeling and Shvt Parameters......Page 131
4.2. Combination Schemes......Page 132
4.3.2. Iterative Sampling Alignment......Page 133
5. Results......Page 134
5.1. Comparison to Other Alignment Schemes......Page 135
6. Conclusion......Page 136
References......Page 137
1. Introduction......Page 140
2.2. Seed sensitivity and specificity......Page 141
3. High-order Seed Patterns and Their Run Probabilities......Page 142
3.1. A recurrence formula f o r hit probability......Page 143
4. The Average Distance Between Successive Non-overlapping Hits......Page 144
4.1.1. Bounding XQ in terms of  Q......Page 145
5. Identifying Good Transition Seeds......Page 146
6 . Conclusion......Page 147
References......Page 148
1.1. Seed optimization......Page 150
1.2. Golomb ruler......Page 152
2.1. Reduction from optimal Golomb ruler design to i.i.d. seed optimization......Page 153
2.2. Counterexample......Page 157
3. Uniform Seed Optimization......Page 158
4. Discussion and Open Problems......Page 159
References......Page 160
Integrating Hierarchical Controlled Vocabularies with OWL Ontology: A Case Study from the Domain of Molecular Interactions Melissa J. Davis, Andrew Newman, Imran Khan, Jane Hunter and Mark A. Ragan......Page 162
1 Introduction......Page 163
2 Results......Page 165
3 Discussion......Page 170
References......Page 171
1.1. Gene Ontology......Page 172
1.2. GO and Similarity between Gene Products......Page 173
1.3. Related Work......Page 174
2.1. Notations......Page 175
2.3. Proposed Similarity Definitions......Page 176
3.1. Dataset......Page 177
4.1. The Use of Edges and Negative Information......Page 178
4.3. More Comparison Results......Page 179
Acknowledgments......Page 180
References......Page 181
1. Introduction......Page 182
3. Event annotation......Page 183
3.1. Annotation scheme......Page 184
4.1. NF-6.B pathway and corpus, the full-text version......Page 186
4.2. NF-KB pathway and corpus, the GENIA version......Page 187
5 . Discussion: Pathway construction from Event annotation......Page 189
5.2. Integration of fragmentary evidences......Page 190
Acknowledgments......Page 191
References......Page 192
1. Introduction......Page 194
2. Method......Page 195
2.1. Dictionary Building......Page 196
2.2. Segmentation......Page 198
3. Results......Page 199
3.1. SCOP family Classfication......Page 200
3.2. GPCR protein subfamily Classi$cation......Page 201
References......Page 203
1. Introduction......Page 204
2.2. Sequence randomization......Page 206
2.4. Statistical significance......Page 207
3. Results and Discussion......Page 208
References......Page 214
1.1. Motivation and Related Work......Page 216
2.2. Motif discovery and scanning......Page 219
3.3. Homology search with predicted secondary structure......Page 223
3.5. Motif prediction and scan......Page 224
References......Page 225
1. Introduction......Page 228
1.2. Eflcient pipeline for detecting ncRNAs......Page 217
1.3. Evaluation......Page 218
2. Preliminaries......Page 229
3. Data reduction......Page 230
4. Initial branching strategy......Page 232
5. Refined branching strategy......Page 233
6. Experiments and results......Page 234
7. Conclusion......Page 236
Bibliography......Page 237
1. Introduction......Page 238
2. Structure Comparison Using Sequence Compression......Page 239
3. Similarity Metric Based on Image and Audio Compression......Page 240
4.1.5. SPC......Page 242
4.3. Data......Page 243
6. Conclusions......Page 244
References......Page 246
1. Introduction......Page 248
2. Background......Page 249
3. Natural Graphs......Page 251
4. Lower Bounds......Page 253
5 . Upper Bounds......Page 254
6. Experiments......Page 256
References......Page 257
Phylogenetic Reconstruction from Complete Gene Orders of Whole Genomes Krister M. Swenson, William Arndt, Jijun Tang and Bernard M. E. Moret......Page 258
1. Introduction......Page 259
2. Methods and Models......Page 261
3. Experimental Design......Page 262
4. Results and Discussion......Page 264
References......Page 266
1. Introduction......Page 268
2. Preliminaries......Page 270
3. Algorithmic Techniques......Page 271
3.1. Handling Non-binary lkees: Refine and Collapse......Page 272
3.2. Algorithmic Techniques for Eflcient Enumeration of Minimal Solutions......Page 273
4. Empirical Performance......Page 275
References......Page 277
1.1. Alignment of minisatellite maps......Page 278
1.2. Previous and new results......Page 279
2. The Duplication History......Page 280
3.1. Computation of optimal trees without insertion......Page 282
3.2. Incorporating insertions in optimal trees......Page 283
4.2. An algorithm for computing an optimal alignment......Page 284
5.2. Detecting directional duplication bias in minisatellites......Page 286
References......Page 288
Appendix I: The Inclusion of Run-length Encoding Scheme......Page 289
1 Introduction......Page 290
2.1 Reaction Retrieval......Page 292
2.2 Building Block Alignment......Page 293
2.3 Pathway Assembly......Page 294
2.4 Scoring Function......Page 295
3 Results and Discussion......Page 297
4 Conclusions......Page 300
References......Page 301
1. Introduction......Page 304
2. Methods......Page 305
3. Experimental Results......Page 307
4. Conclusions......Page 312
References......Page 313
1. Introduction......Page 314
2. Problem Formulation......Page 316
3. Clustering across windows......Page 317
4. Segmentation Algorithm......Page 319
5 . Experiments......Page 320
References......Page 323
1. Introduction......Page 324
2. Boolean Networks......Page 325
3. Model Checking......Page 326
3.2. Symbolic Encodings of Kripke Structures......Page 327
3.3. Temporal Logics......Page 328
4. A Symbolic Model Checking Approach to Finding Control Policies......Page 329
6.1. Scalability......Page 331
6.2. Application To D. Melanogaster Embryo Development......Page 332
References......Page 334
1 Introduction......Page 338
2.1 Estimation of Pairwise Relatedness......Page 339
2.2 Estimation of Allele Frequencies from Known Pedigree......Page 341
2.3 Unknown Pedigree......Page 342
2.4 Algorithm......Page 343
3 Results and Discussion......Page 344
References......Page 346
1. Introduction......Page 350
2. A Probabilistic Model......Page 351
3. Technical Lemmas......Page 352
4. When the Inconsistency Error Parameter Is Known......Page 354
5. When Parameters Are Not Known......Page 355
6. Tuning the Dissimilarity Measure......Page 357
7. Experimental Results......Page 358
References......Page 359
1 Introduction......Page 360
2.1 DPS Representation......Page 362
2.2 Scoring Function and Problem Definition......Page 363
3.1 Factor Tree Representation......Page 364
3.2 Branch and Bound Approach......Page 365
4 Experimental Results......Page 366
5 Conclusion......Page 367
References......Page 368
Appendix......Page 369
1. Introduction......Page 370
2. Inversion Detection......Page 371
3. Anchored Deletion Detection......Page 374
4. Experimental Results......Page 377
References......Page 379
1.1. Gene Prediction Combiners......Page 380
1.2. Diversity Combiners and Wise Crowds......Page 381
2.1. Approach......Page 382
3.1. Training and Test Sets......Page 384
3.2. Evaluation......Page 385
4. Discussion......Page 386
References......Page 388
Comparing and Analysing Gene Expression Patterns Across Animal Species Using 4DXpress Yannick Haudry, Chuang Kee Ong, Laurence Ettwiller, Hugo Berube, Ivica Letunic, Misha Kapushesky, Paul-Daniel Weeber, X i Wang, Julien Gagneur, Charles Girardot, Detl......Page 390
2. 4DXpress......Page 392
2.1.2. Developmental Stages......Page 394
3. Co-Expression Analysis......Page 395
4.Application......Page 396
References......Page 398
1 Introduction......Page 400
2 Near-Sigmoid Modeling......Page 402
2.2 Statistical significance of near-sigmoidfit......Page 403
3 S. pombe DNA Replication Data Analysis using Near-Sigrnoid Modeling......Page 404
3.3 Early replication timing of chrZZZ relative to chrZ & chrZZ......Page 405
3.5 Higher efficiency of telomeres compared to the other regions......Page 406
4 Discussion......Page 407
References......Page 408
Author Index......Page 410