Selected Topics in Post-Genome Knowledge Discovery

The following sections are included:

• Contents

• Foreword

• Preface

The development of a dynamic-programming algorithm has three basic components: the recurrence relation for defining the value of an optimal solution, the tabular computation for computing the value of an optimal solution, and the traceback for delivering an optimal solution. Here we introduce these basic ideas by developing dynamic-programming solutions for problems from different application areas. Then we focus on some dynamic-programming strategies for analyzing biomolecular sequences, including pairwise sequence alignment and multiple sequence alignment.

A pathway is a collection of two or more proteins/molecules connected by their interactions within and around a cell. We study the informatics and evolutionary issues of pathways. Similar to the definition of homology in the comparison of nucleotide and protein sequences, we define homologous pathways as pathways that are evolved from the same ancestral pathway. We first present a survey of existing pathway databases and discuss their format of pathway representation. Then, our pathway representation, the SLIPR format, is presented. It is a semilinear graphic representation of nodes (proteins) and modes (interactions). Pathways in SLIPR format enable pathway comparisons for evolutionary relationship and large-scale pathway database searches. We also discuss how one can map out orthologous pathways, achieving a predictive power on functional assignment of novel genes, once the pathway is understood well-enough in a closely-related species.

Gene networks play a central role in systems biology. This paper is a tutorial on a computational strategy focused on gene network inference and biopathway modeling following our recent contributions to the Genomic Object Net.

Data mining is the semi-automatic discovery of patterns, associations, changes, anomalies, and statistically significant structures and events in data. Traditional data analysis is assumption driven in the sense that a hypothesis is formed and validated against the data. Data mining, in contrast, is data driven in the sense that patterns are automatically extracted from data. The goal of this tutorial is to provide an introduction to data mining techniques. The focus will be on methods appropriate for mining massive datasets using techniques from scalable and high performance computing. The techniques covered include association rules, sequence mining, decision tree classification, and clustering. Some aspects of preprocessing and postprocessing are also covered. The problem of predicting contact maps for protein sequences is used as a detailed case study.

The material presented here is compiled by LW based on the original tutorial slides of MJZ at the 2002 Post-Genome Knowledge Discovery Programme in Singapore.