Problem Solving Handbook in Computational Biology and Bioinformatics

This chapter gives some simple, useful techniques for approximating the p-values of various types of optimal alignment scores. It starts with general techniques: if, e.g., a dynamic programming computation has probabilistically independent inputs, its successive states form a Markov chain. Thus, if the states are not too numerous, a “Markov computation” yields their distribution. The chapter reviews the three extreme-value distributions, which are relevant to approximating the distribution of random maxima, in the same way the normal distribution is relevant to approximating the distribution of random sums. In general, convergence to an extreme-value distribution is often painfully slow, so the Poisson approximation for counting rare and weakly dependent events can be a more flexible tool for approximating the distribution of maxima. In particular, the extreme-value and Poisson distributionsyield an approximate distribution for the optimal local alignment score of two random sequences, and a finite-size correction can increase the accuracy of statistical approximations if the sequences are relatively short. Moreover, the concept of “islands” permits many statistical approximation problems in local alignment to be transformed to combinatorial problems. Finally, the “Independent Diagonals Approximation” broadens the application of many of the previous methods, and an “Independent Alignments Approximation” converts many alignment variants into the combinatorial problem of determining an “effective length”.

One of the primary genetic events shaping an autosomal chromosome is recombination. This is a process that occurs during meiosis, in eukaryotes, that results in the offsprings having different combinations of (homologous) genes, or chromosomal segments, of the two parents. The presence of these recombination events in the evolutionary history of each chromosome complicates the genetic landscape of a population, and understanding the manifestations of these genetic exchanges in the chromosome sequences has been a subject of intense curiosity (see [Hud83, Gri99, HSW05] and citations therein).

Phylogenetic networks are special graphs that generalize phylogenetic trees to allow for modeling of non-treelike evolutionary histories. The ability to sequence multiple genetic markers from a set of organisms and the conflicting evolutionary signals that these markers provide in many cases, have propelled research and interest in phylogenetic networks to the forefront in computational phylogenetics. Nonetheless, the term ‘phylogenetic network‘ has been generically used to refer to a class of models whose core shared property is tree generalization. Several excellent surveys of the different flavors of phylogenetic networks and methods for their reconstruction have been written recently. However, unlike these surveys, this chapte focuses specifically on one type of phylogenetic networks, namely evolutionary phylogenetic networks, which explicitly model reticulate evolutionary events. Further, this chapter focuses less on surveying existing tools, and addresses in more detail issues that are central to the accurate reconstruction of phylogenetic networks.

Complex networks of interactions between genes, proteins, and other molecules choreograph cellular processes. The interactions that are active in the cell change over time, both as a natural outcome of the cell‘s natural life cycle and in response to external signals. The set of active interactions, called the response network, are likely to be significantly different between a normally-functioning cell and a diseased cell. The wide availability of DNA microarray data and experimentallydetermined interaction networks has made it possible to automatically compute response networks. This chapter surveys algorithms that have been developed to compute response networks.