INFORMS Journal on Computing articles from September 2004

INFORMS Journal on Computing archives from September 2004

From the guest editor for the special issue on computational molecular biology/bioinformatics.
September 22, 2004... We are in a revolution. The Human Genome Project brought biology from an information-poor to an information-rich science, and this has caused a permanent change in its research, with causal effects on medical research. In fact, it will not be...

Palindromes in SARS and other coronaviruses.
September 22, 2004... With the identification of a novel coronavirus associated with the severe acute respiratory syndrome (SARS), computational analysis of its RNA genome sequence is expected to give useful clues to help elucidate the origin, evolution, and...

Searching for multiple words in a Markov sequence.
September 22, 2004... The theory of the discrete-time Markovian arrival process (DMAP) can be applied to some statistical problems encountered when searching for multiple words in a Markov sequence. Such word searches are often emphasized in studies of the human...

Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms.
September 22, 2004... In this paper we address the pure parsimony haplotyping problem: Find a minimum number of haplotypes that explains a given set of genotypes. We prove that the problem is APX-hard and present a [2.sup.k-1]-approximation algorithm for the case in...

Computational problems in noisy SNP and haplotype analysis: block scores, block identification, and population stratification.
September 22, 2004... The study of haplotypes and their diversity in a population is central to disease-association research. We study several problems arising in haplotype block partitioning. Our objective function is the total number of distinct haplotypes in...

Global optimization of Morse clusters by potential energy transformations.
September 22, 2004... The Morse potential is a simple model for the potential energy of atoms with a single parameter [rho] that determines the width of the potential well and allows a wide variety of materials to be modeled. Morse clusters are particularly...

A semidefinite programming approach to side chain positioning with new rounding strategies.
September 22, 2004... Side chain positioning is an important subproblem of the general protein-structure-prediction problem, with applications in homology modeling and protein design. The side chain positioning problem takes a fixed backbone and a protein sequence...

Protein threading: from mathematical models to parallel implementations.
September 22, 2004... This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These models allow for an efficient...

Optimizing an empirical scoring function for transmembrane protein structure determination.
September 22, 2004... We examine the problem of transmembrane protein structure determination. Like many questions that arise in biological research, this problem cannot be addressed generally by traditional laboratory experimentation alone. Instead, an approach...

Optimal solutions for the closest-string problem via integer programming.
September 22, 2004... In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set S = {[s.sup.1],[s.sup.2],..., [s.sup.n]} of strings, each string with length m, find a center string t of length m minimizing d, such...

Multiple sequence alignment as a facility-location problem.
September 22, 2004... A connection is made between certain multiple-sequence alignment problems and facility-location problems, and the existence of a PTAS (polynomial-time approximation scheme) for these problems is shown. Moreover, it is shown that multiple...

Dynamic programming based approximation algorithms for sequence alignment with constraints.
September 22, 2004... Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I [??] X and J [??] Y with maximum similarity score under a given scoring scheme. In several applications,...

The fine structure of galls in phylogenetic networks.
September 22, 2004... A phylogenetic network is a generalization of a phylogenetic tree, allowing properties that are not tree-like. With the growth of genomic data, much of which does not fit ideal tree models, there is greater need to understand the algorithmics...

Steiner trees and 3-D macromolecular conformation.
September 22, 2004... One of the key issues in biochemistry and molecular modelling is the determination of 3-D minimum-energy configurations (MECs) for macromolecular structures such as proteins and DNA. Steiner minimal trees are seen as a useful algorithmic...

Appreciation to referees.
September 22, 2004... On behalf of the Editorial Board, I would like to thank the following people, who acted as Referees during the past year. An asterisk indicates two or more reviews. Abbass, Hussein, University of New South Wales, Australia Achar, Ram,...