Catálogo de publicaciones - libros

Elementary flux modes (EFMs)—formalized metabolic pathways—are central and comprehensive tools for metabolic network analysis under steady state conditions. They act as a generating basis for all possible flux distributions and, thus, are a minimal (constructive) description of the solution space. Algorithms to compute EFMs descend from computational geometry; they are mostly synonymous to the enumeration of extreme rays of polyhedral cones. This problem is combinatorially complex, and algorithms do not scale well. Here, we introduce new concepts for the enumeration of adjacent rays, which is one of the critical and stubborn facets of the algorithms. They rely on variants of k-d-trees to store and analyze bit sets representing (intermediary) extreme rays. allow for speed-up of computations primarily for low-dimensional problems. Extensions to to narrow candidate pairs for adjacency tests scale with problem size, yielding speed-ups on the order of one magnitude relative to current algorithms. Additionally, fast algebraic tests can easily be used in the framework. This constitutes one step towards EFM analysis at the whole-cell level.

The study of variation in DNA sequences, within the framework of phylogeny or population genetics, for instance, is one of the most important subjects in modern genomics. We here present a new linear-time algorithm for finding maximal -regions in alignments of three sequences, which can be used for the detection of segments featuring a certain degree of similarity, as well as the boundaries of distinct genomic environments such as gene clusters or haplotype blocks. -regions are defined as these which have a center sequence whose Hamming distance from any of the alignment rows is at most , and their determination in the general case is known to be NP-hard.

Deoxyribonucleic acid (DNA) sequencing is an important task in computational biology. In recent years the specific problem of DNA sequencing by hybridization has attracted quite a lot of interest in the optimization community. However, in contrast to the development of metaheuristics, the work on simple constructive heuristics hardly received any attention. This is despite the fact that well-working constructive heuristics are often an essential component of succesful metaheuristics. It is exactly this lack of constructive heuristics that motivated the work presented in this paper. The results of our best constructive heuristic are comparable to the results of the best available metaheuristics, while using less computational resources.

Sequencing by Hybridization (SBH) is a method for reconstructing a DNA sequence based on its -mer content. This content, called the of the sequence, can be obtained from hybridization with a universal DNA chip. The main shortcoming of SBH is that it reliably reconstructs only sequences of length at most square root of the size of the chip. Frieze et al. [9] showed that by using gapped probes, SBH can reconstruct sequences with length that is linear in the size of the chip. In this work we investigate the optimal placement of the gaps in the probes, and give an algorithm for finding nearly optimal gap placement. Using our algorithm, we obtain a chip design which is more efficient than the chip of Frieze et al.

The list of species whose complete DNA sequence have been read, is growing steadily and it is believed that comparative genomics is in its early days[12]. Permutations patterns (groups of genes in some “close” proximity) on gene sequences of genomes across species is being studied under different models, to cope with this explosion of data. The challenge is to (intelligently and efficiently) analyze the genomes in the context of other genomes. In this paper we present a generalized model that uses three notions, permutation patterns (with gap ), genome clusters, via , > 1, parameter, and, possible multiplicity in the patterns. The task is to automatically discover all permutation patterns (with possible multiplicity), that occur with gap in at least of the given genomes. We present time algorithm where is the number of sequences, each defined on Σ, is the size of the input and is the size of the maximal gene clusters that appear in at least of the genomes.

We introduce a novel generative probabilistic model for segmentation problems in molecular sequence analysis. All segmentations that satisfy given minimum segment length requirements are equally likely in the model. We show how segmentation-related problems can be solved with similar efficacy as in hidden Markov models. In particular, we show how the best segmentation, as well as posterior segment class probabilities in individual sequence positions can be computed in () time in case of segment classes and a sequence of length .