Given a set $\Sigma$ of bipartitions of some finite set X of cardinality at least 2, one can associate to $\Sigma$ a canonical X-labeled graph $\mathcal{B}(\Sigma)$, called the Buneman graph. This graph has several interesting mathematical properties—for example, it is a median network and therefore an isometric subgraph of a hypercube. It is commonly used as a tool in studies of DNA sequences gathered from populations. In this paper, we present some results concerning the cut vertices of $\mathcal{B}(\Sigma)$, i.e., vertices whose removal disconnect the graph, as well as its blocks or 2-connected components—results that yield, in particular, an intriguing generalization of the well-known fact that $\mathcal{B}(\Sigma)$ is a tree if and only if any two splits in $\Sigma$ are compatible.

Inspired by recent discovery that human disease phenome shows a modular organization on the genetic landscape, we introduce a network-module based method towards phenotype-genotype association inference and disease-gene identification. This approach integrates protein-protein interaction network, phenotype similarity network and known phenotype-genotype associations, and then decomposes the resulted assembled network into modules (or communities) wherein we identified and prioritized the disease genes from the candidates within the loci associated with the query disease using a linear regression model and concordance score. For the known phenotype-gene associations in the OMIM database, we used the leave-one-out validation to evaluate the feasibility of our method, and successfully ranked known disease genes at top 1 in 887 out of 1807 cases. Moreover, applying this approach on 850 OMIM loci characterized by an unknown molecular basis, we propose high-probability candidates for 81 genetic diseases.

Phylogenetic trees correspond one-to-one to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetic algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4.

Abstract Summary: We introduce a WWW-based tool that is able to compare two alternative multiple alignments of a given sequence set. Regions where both alignments coincide are color-coded to visualize the local agreement between the two alignments and to identify those regions that can be considered to be reliably aligned. Availability: http://bibiserv.techfak.uni-bielefeld.de/altavist/ Contact: [email protected] * To whom correspondence should be addressed.

MOTIVATION: During evolution, functional regions in genomic sequences tend to be more highly conserved than randomly mutating 'junk DNA' so local sequence similarity often indicates biological functionality. This fact can be used to identify functional elements in large eukaryotic DNA sequences by cross-species sequence comparison. In recent years, several gene-prediction methods have been proposed that work by comparing anonymous genomic sequences, for example from human and mouse. The main advantage of these methods is that they are based on simple and generally applicable measures of (local) sequence similarity; unlike standard gene-finding approaches they do not depend on species-specific training data or on the presence of cognate genes in data bases. As all comparative sequence-analysis methods, the new comparative gene-finding approaches critically rely on the quality of the underlying sequence alignments. RESULTS: Herein, we describe a new implementation of the sequence-alignment program DIALIGN that has been developed for alignment of large genomic sequences. We compare our method to the alignment programs PipMaker, WABA and BLAST and we show that local similarities identified by these programs are highly correlated to protein-coding regions. In our test runs, PipMaker was the most sensitive method while DIALIGN was most specific. AVAILABILITY: The program is downloadable from the DIALIGN home page at http://bibiserv.techfak.uni-bielefeld.de/dialign/.

MOTIVATION: DIALIGN is a new method for pairwise as well as multiple alignment of nucleic acid and protein sequences. While standard alignment programs rely on comparing single residues and imposing gap penalties, DIALIGN constructs alignments by comparing whole segments of the sequences. No gap penalty is employed. This point of view is especially adequate if sequences are not globally related, but share only local similarities, as is the case in genomic DNA sequences and in many protein families. RESULTS: Using four different data sets, we show that DIALIGN is able correctly to align conserved motifs in protein sequences. Alignments produced by DIALIGN are compared systematically to the results of five other alignment programs. AVAILABILITY: DIALIGN is available to the scientific community free of charge for non-commercial use. Executables for various UNIX platforms including LINUX can be downloaded at http://www.gsf.de/biodv/dialign.html CONTACT: werner, [email protected]

MOTIVATION: DCA is a new computer program for multiple sequence alignment which utilizes a 'divide-and-conquer' type of heuristic approach. AVAILABILITY: The algorithm is freely available from http://bibiserv.TechFak.Uni-Bielefeld.DE/dca/.

Procedures for determining the feasibility of lower and upper bounds on Euclidean distances of fixed dimension play a central role in the analysis of many kinds of scientific data. Shown in this paper is how results from graph optimization theory can be used to solve the feasibility problem in one dimension, subject to the condition that the order of the points along the real line is known. The solution is used to derive a PSPACE, $O( n^{3}\cdot n! )$-time sequential algorithm for finding one-dimensional representations subject to arbitrary distance (and order) constraints. The wider applicability of these results in measurement theory is discussed, in particular, Roy’s elegant proofs of the classical representation theorems for interval orders and semiorders, and they are used to obtain a new representation theorem for a ternary relation called $\varepsilon $-collinearity.