Search

Woolly mammoths and living elephants are characterized by major phenotypic differences that have allowed them to live in very different environments. To identify the genetic changes that underlie the suite of woolly mammoth adaptations to extreme cold, we sequenced the nuclear genome from three Asian elephants and two woolly mammoths, and we identified and functionally annotated genetic changes unique to woolly mammoths. We found that genes with mammoth-specific amino acid changes are enriched in functions related to circadian biology, skin and hair development and physiology, lipid metabolism, adipose development and physiology, and temperature sensation. Finally, we resurrected and functionally tested the mammoth and ancestral elephant TRPV3 gene, which encodes a temperature-sensitive transient receptor potential (thermoTRP) channel involved in thermal sensation and hair growth, and we show that a single mammoth-specific amino acid substitution in an otherwise highly conserved region of the TRPV3 channel strongly affects its temperature sensitivity.

We develop techniques to estimate the statistical significance of gap-free alignments between two genomic DNA sequences, using human–mouse alignments as an example. The sequences are assumed to be sufficiently similar that some but not all of the neutrally evolving regions (i.e., those under no evolutionary constraint) can be reliably aligned. Our goal is to model the situation in which the neutral rate of evolution, and hence the extent of the aligning intervals, varies across the genome. In some cases, this permits the weaker of two matches to be judged as less likely to have arisen by chance, provided it lies in a genomic interval with a high level of background divergence. We employ a hidden Markov model to capture variations in divergence rates and assign probability values to gap-free alignments using techniques of Dembo and Karlin, which are related to those used for the same purpose by BLAST. Our methods are illustrated in detail using a 1.49 Mb genomic region. Results obtained from the analysis of human chromosome 22 using these techniques are also provided.

Williams syndrome is a complex developmental disorder that results from the heterozygous deletion of a approximately 1.6-Mb segment of human chromosome 7q11.23. These deletions are mediated by large (approximately 300 kb) duplicated blocks of DNA of near-identical sequence. Previously, we showed that the orthologous region of the mouse genome is devoid of such duplicated segments. Here, we extend our studies to include the generation of approximately 3.3 Mb of genomic sequence from the mouse Williams syndrome region, of which just over 1.4 Mb is finished to high accuracy. Comparative analyses of the mouse and human sequences within and immediately flanking the interval commonly deleted in Williams syndrome have facilitated the identification of nine previously unreported genes, provided detailed sequence-based information regarding 30 genes residing in the region, and revealed a number of potentially interesting conserved noncoding sequences. Finally, to facilitate comparative sequence analysis, we implemented several enhancements to the program, including the addition of links from annotated features within a generated percent-identity plot to specific records in public databases. Taken together, the results reported here provide an important comparative sequence resource that should catalyze additional studies of Williams syndrome, including those that aim to characterize genes within the commonly deleted interval and to develop mouse models of the disorder.

ABSTRACTThe major distal regulatory sequence for the β-globin gene locus, the locus control region (LCR), is composed of multiple hypersensitive sites (HSs). Different models for LCR function postulate that the HSs act either independently or synergistically. To test these possibilities, we have constructed a series of expression cassettes in which the gene encoding the enhanced green fluorescent protein (EGFP) is under the control of DNA fragments containing single and multiple HSs of the LCR. LCR DNA fragments containing only the minimal region needed for position-independent expression (HS cores) or containing cores plus flanking sequences (HS units) were compared to ascertain whether conserved sequences between the HS cores contributed to enhancement. Expression of these constructs was measured after targeted integration into three defined loci in murine erythroleukemia cells using recombinase-mediated cassette exchange. At all three marked loci, synergistic enhancement of expression was observed in cassettes containing a combination of HS2, HS3, and HS4 units. In contrast, HS2, HS3, and HS4 cores (without flanking sequences) give an activity equivalent to the sum of the activities of the individual HS cores. These data suggest a model in which an HS core plus flanking regions, bound by specific proteins, forms a structure needed for interaction with other HS units to confer strong enhancement by the LCR. The three targeted integration sites differ substantially in their permissivity for expression, but even the largest LCR construct tested could not overcome these position effects to confer equal expression at all three sites.

The major distal regulatory sequence for the β-globin gene locus, the locus control region (LCR), is composed of multiple hypersensitive sites (HSs). Different models for LCR function postulate that the HSs act either independently or synergistically. To test these possibilities, we have constructed a series of expression cassettes in which the gene encoding the enhanced green fluorescent protein (EGFP) is under the control of DNA fragments containing single and multiple HSs of the LCR. LCR DNA fragments containing only the minimal region needed for position-independent expression (HS cores) or containing cores plus flanking sequences (HS units) were compared to ascertain whether conserved sequences between the HS cores contributed to enhancement. Expression of these constructs was measured after targeted integration into three defined loci in murine erythroleukemia cells using recombinase-mediated cassette exchange. At all three marked loci, synergistic enhancement of expression was observed in cassettes containing a combination of HS2, HS3, and HS4 units. In contrast, HS2, HS3, and HS4 cores (without flanking sequences) give an activity equivalent to the sum of the activities of the individual HS cores. These data suggest a model in which an HS core plus flanking regions, bound by specific proteins, forms a structure needed for interaction with other HS units to confer strong enhancement by the LCR. The three targeted integration sites differ substantially in their permissivity for expression, but even the largest LCR construct tested could not overcome these position effects to confer equal expression at all three sites.

The core of DNase hypersensitive site (HS) 2 from the β-globin locus control region is a potent enhancer of globin gene expression. Although it has been considered to contain only positive cis-regulatory sequences, our study of the enhancement conferred by segments of HS2 in erythroid cells reveals a novel negative element. Individual cis-regulatory elements from HS2 such as E boxes or Maf-response elements produced as great or greater enhancement than the intact core in mouse erythroleukemia (MEL) cells, indicating the presence of negative elements within HS2. A deletion series through HS2 revealed negative elements at the 5′ and 3′ ends of the core. Analysis of constructs with and without the 5′ negative element showed that the effect is exerted on the promoters of globin genes expressed at embryonic, fetal, or adult stages. The negative effect was observed in bipotential human cells (K562 and human erythroleukemia (HEL) cells), proerythroblastic mouse (MEL) cells, and normal adult human erythroid cells. The novel negative element also functions after stable integration into MEL chromosomes. Smaller deletions at the 5′ end of the HS2 core map the negative element within a 20-base pair region containing two conserved sequences.

For aligning DNA sequences that differ only by sequencing errors, or by equivalent errors from other sources, a greedy algorithm can be much faster than traditional dynamic programming approaches and yet produce an alignment that is guaranteed to be theoretically optimal. We introduce a new greedy alignment algorithm with particularly good performance and show that it computes the same alignment as does a certain dynamic programming algorithm, while executing over 10 times faster on appropriate data. An implementation of this algorithm is currently used in a program that assembles the UniGene database at the National Center for Biotechnology Information.

In database searches for sequence similarity, matches to a distinct sequence region (e.g., protein domain) are frequently obscured by numerous matches to another region of the same sequence. In order to cope with this problem, algorithms are developed to discard redundant matches. One model for this problem begins with a list of intervals, each with an associated score; each interval gives the range of positions in the query sequence that align to a database sequence, and the score is that of the alignment. If interval I is contained in interval J, and I's score is less than J's, then is said to be dominated by J. The problem is then to identify each interval that is dominated by at least K other intervals, where K is a given level of "tolerable redundancy." An algorithm is developed to solve the problem in O(NlogN) time and O(N*)space, where N is the number of intervals and N* is a precisely defined value that never exceeds N and is frequently much smaller. This criterion for discarding database hits has been implemented in the Blast program, as illustrated herein with examples. Several variations and extensions of this approach are also described.

Mutations in myosin XV are responsible for congenital profound deafness DFNB3in humans and deafness and vestibular defects in shaker 2 mice. By combining direct cDNA analyses with a comparison of 95.2 kb of genomic DNA sequence from human chromosome 17p11.2 and 88.4 kb from the homologous region on mouse chromosome 11, we have determined the genomic and mRNA structures of the human (MYO15) and mouse (Myo15) myosin XV genes. Our results indicate that full-length myosin XV transcripts contain 66 exons, are >12 kb in length, and encode 365-kDa proteins that are unique among myosins in possessing very long ∼1200-aa N-terminal extensions preceding their conserved motor domains. The tail regions of the myosin XV proteins contain two MyTH4 domains, two regions with similarity to the membrane attachment FERM domain, and a putative SH3 domain. Northern and dot blot analyses revealed that myosin XV is expressed in the pituitary gland in both humans and mice. Myosin XV transcripts were also observed by in situhybridization within areas corresponding to the sensory epithelia of the cochlea and vestibular systems in the developing mouse inner ear. Immunostaining of adult mouse organ of Corti revealed that myosin XV protein is concentrated within the cuticular plate and stereocilia of cochlear sensory hair cells. These results indicate a likely role for myosin XV in the formation or maintenance of the unique actin-rich structures of inner ear sensory hair cells.

As part of a large scale mouse Expressed Sequence Tag (EST) project to identify molecules involved in the initiation of mammalian development, a homolog of the Drosophilacornichongene was detected as a mouse maternal transcript present in the two-cell embryo. Cornichonis a multigene family in the mouse: the new gene, Cnih, maps to mouse chromosome 10, another cornichonhomolog, Cnil, maps to chromosome 14 and two additional cornichon-related loci, possibly pseudogenes, localize to chromosomes 3 and 10, respectively. Cnihencodes an open reading frame (ORF) of 144 amino acids that is 93% homologous (68% identical) to the Drosophilaprotein, whereas the ORF of Cnilcontains two extra polypeptide regions not found in these other proteins. Transcripts of Cnihare highly abundant in the full grown oocyte and the ovulated unfertilized egg, while Cnilmessage is only detectable after activation of the embryonic genome at the eight-cell stage. In situ hybridization shows specific localization of Cnihtranscripts to ovarian oocytes. The lack of cytoplasmic polyadenylation of the maternally inherited Cnihtranscript suggests that CnihmRNA is translated in the full grown oocyte before, but not after, ovulation. In Drosophila, cornichonis involved in the establishment of both anterior-posterior and dorso-ventral polarity via the epidermal growth factor (EGF)-receptor signaling pathway. Finding Cnihin the mammalian oocyte opens a new perspective on the investigation of EGF-signaling in the oocyte.

Human chromosome 5q11.2–q13.3 and its ortholog on mouse chromosome 13 contain candidate genes for an inherited human neurodegenerative disorder called spinal muscular atrophy (SMA) and for an inherited mouse susceptibility to infection with Legionella pneumophila(Lgn1). These homologous genomic regions also have unusual repetitive organizations that create practical difficulties in mapping and raise interesting issues about the evolutionary origin of the repeats. In an attempt to analyze this region in detail, and as a way to identify additional candidate genes for these diseases, we have determined the sequence of 179 kb of the mouse Lgn1/SMA interval. We have analyzed this sequence using BLAST searches and various exon prediction programs to identify potential genes. Since these methods can generate false-positive exon declarations, our alignments of the mouse sequence with available human orthologous sequence allowed us to discriminate rapidly among this collection of potential coding regions by indicating which regions were well conserved and were more likely to represent actual coding sequence. As a result of our analysis, we accurately mapped two additional genes in the SMA interval that can be tested for involvement in the pathogenesis of SMA. While no new Lgn1candidates emerged, we have identified new genetic markers that exclude Smnas an Lgn1candidate. In addition to providing important resources for studying SMA and Lgn1,our data provide further evidence of the value of sequencing the mouse genome as a means to help with the annotation of the human genomic sequence and vice versa.

A new approach to rapid sequence comparison, basic local alignment search tool (BLAST), directly approximates alignments that optimize a measure of local similarity, the maximal segment pair (MSP) score. Recent mathematical results on the stochastic properties of MSP scores allow analysis of the performance of this method as well as the statistical significance of alignments it generates. The basic algorithm is simple and robust; it can be implemented in a number of ways and applied in a variety of contexts including straight-forward DNA and protein sequence database searches, motif searches, gene identification searches, and in the analysis of multiple regions of similarity in long DNA sequences. In addition to its flexibility and tractability to mathematical analysis, BLAST is an order of magnitude faster than existing sequence comparison tools of comparable sensitivity. Copyright 1990 Academic Press

We have previously reported, on the basis of transfection experiments, the existence of a silencer element in the 5′-flanking region of the human embryonic (ε) globin gene, located at −270 base pairs 5′ to the cap site, which provides negative regulation for this gene. Experiments in transgenic mice suggest the physiological importance of this ε-globin silencer, but also suggest that down-regulation of ε-globin gene expression may involve other negative elements flanking the ε-globin gene. We have now extended the analysis of ε-globin gene regulation to include the flanking region spanning up to 6 kilobase pairs 5′ to the locus control region using reporter gene constructs with deletion mutations and transient transfection assays. We have identified and characterized other strong negative regulatory regions, as well as several positive regions that affect transcription activation. The negative regulatory regions at −3 kilobase pairs (εNRA-I and εNRA-II), flanked by a positive control element, has a strong effect on the ε-globin promoter both in erythroid K562 and nonerythroid HeLa cells and contains several binding sites for transcription factor GATA-1, as evidenced from DNA-protein binding assays. The GATA-1 sites within εNRA-II are directly needed for negative control. Both εNRA-I and εNRA-II are active on a heterologous promoter and hence appear to act as transcription silencers. Another negative control region located at −1.7 kilobase pairs (εNRB) does not exhibit general silencer activity as εNRB does not affect transcription activity when used in conjunction with an ε-globin minimal promoter. The negative effect of εNRB is erythroid specific, but not stage-specific as it can repress transcription activity in both K562 erythroid cells as well as in primary cultures of adult erythroid cells. Phylogenetic DNA sequence comparisons with other primate and other mammalian species show unusual degree of flanking sequence homology for the ε-globin gene, including in several of the regions identified in these functional and DNA-protein binding analyses, providing alternate evidence for their potential importance. We suggest that the down-regulation of ε-globin gene expression as development progresses involves complex, cooperative interactions of these negative regulatory elements, εNRA-I/εNRA-II, εNRB, the ε-globin silencer and probably other negative and positive elements in the 5′-flanking region of the ε-globin gene.

Summary Techniques are emerging which automatically determine the effects of rounding error upon numerical methods of a certain type. Meaningful testing presupposes a reasonable basis for comparison. Typically, the error's effects upon a given method are compared either (i) with the effects of perturbing the computational problem or (ii) with the effects of rounding error upon a competing method. We show that the result of a type (ii) comparison often remains valid when the two methods are adapted for “sparse” data, though the comparison might be based upon a model of error propagation which requires that special care be taken. This observation sometimes provides a rationale for preferring comparisons (ii), since the results of type (i) comparisons may well not carry over to sparse data.

The sequence of virtually the entire cluster of β-like globin genes has been determined from several mammals, and many regulatory regions have been analyzed by mutagenesis, functional assays, and nuclear protein binding studies. This very large amount of sequence and functional data needs to be compiled in a readily accessible and usable manner to optimize data analysis, hypothesis testing, and model building. We report a Globin Gene Server that will provide this service in a constantly updated manner when fully implemented. The Server has two principal functions. The first (currently available) provides an annotated multiple alignment of the DNA sequences throughout the gene cluster from representatives of all species analyzed. The second compiles data on functional and protein binding assays throughout the gene cluster. A prototype of this compilation using the aligned 5' flanking region of β-globin genes from five species shows examples of (1) well-conserved regions that have demonstrated functions, including cases in which the functional data are in apparent conflict, (2) proposed functional regions that are not well conserved, and (3) conserved regions with no currently assigned function. Such an electronic genetic analysis leads to many readily testable hypotheses that were not immediately apparent without the multiple alignment and compilation. The Server is accessible via E-mail on computer networks, and printed results can be obtained by request to the authors. This prototype will be a helpful guide for developing similar tools for many genomic loci. Copyright 1994, 1999 Academic Press

The locus control region (LCR) of mammalian β-globin genes covers at least 17 kb at the 5′ end of the gene cluster and has been implicated in chromatin domain opening, enhancement, and insulation from neighboring sequences. Functional dissection of the LCR has defined the minimal cores for four of the five major DNase hypersensitive sites (HSs) that mark this regulatory region. To examine fully the patterns of conserved sequences in the mammalian homologs to the β-globin LCR, we determined the complete DNA sequence of the galago β-globin LCR and completed previously unsequenced regions of the rabbit LCR. Simultaneous alignment of these sequences with the human, goat, and mouse LCRs revealed conserved sequences (phylogenetic footprints) detected using three largely independent methods. The most highly conserved segments are found both within the HS cores and in some but not all regions flanking the cores. These results argue for an extended pattern of well-conserved sequences, many of which lie outside the minimal cores, and we show that a key sequence required for domain opening by the region including HS3 maps about 1 kb 5′ to the minimal core. Differential phylogenetic footprints, containing sequences conserved in nonhuman mammals but not in humans, are found primarily around HS3, consistent with some species-specific differences in function that may be important for differences in hemoglobin switching during development.

Information on gene expression and regulation is expanding rapidly, and the complexity of the experimental design and data makes unique demands on databases to store the results. We describe a prototype database containing experimental results on the expression of mammalian β-like globin genes, along with several query methods for accessing the information. The database has tables for DNA transfer experiments, protein–DNA binding results, and positions of DNase hypersensitive sites, which make extensive use of nested data structures. Comparison of data from various mammals is accomplished by providing a common coordinate system via a simultaneous alignment of matching DNA sequences. Interactive access to the database is available at a site called theGlobin Gene Serveron the World Wide Web (http://globin.cse. psu.edu). This software should be useful for any genetic system in which DNA sequence data are available.

The roles of each DNase hypersensitive site (HS), and the DNA sequences between them, in the activity of the locus control region of the mammalian β-globin gene domain were examined by placing human and rabbit restriction fragments containing the cores of HS2, HS3, HS4, and HS5, along with varying amounts of flanking DNA, upstream of a hybrid ∊-globin-luciferase reporter gene and testing for effects on expression both prior to and after integration into the chromosomes of K562 cells, a human erythroid cell line. Prior to integration, fragments containing HS2 enhanced expression to the greatest extent, and the modest enhancement by some fragments containing HS3 correlated with the presence of a well-conserved binding site for AP1/NFE2. The stronger effects of larger locus control region DNA fragments in clones of stably transfected cells indicates a role for sequences outside the HS cores after integration into the genome. The strong effect of a 1.9-kilobase HindIII fragment containing HS3 after, but not prior to, integration argues for the presence of a chromatin domain-opening activity. Use of a rabbit DNA fragment containing both HS2 and HS3 demonstrated a synergistic interaction between the two HSs when their natural context and spacing are preserved.

Hypersensitive site 3 (HS3) of the β-like globin locus control region has been implicated as an important regulator of the β-like globin genes, but the trans factors that bind HS3 have only been partially characterized. Using a five-species alignment (human, galago, rabbit, goat, and mouse) that represents 370 million years of evolution, we have identified 24 phylogenetic footprints in the HS3 core and surrounding regions. Probes corresponding to the human sequence at each footprint have been used in binding studies to identify the nuclear factors that bind within and near these conserved sequence elements. Among the high-affinity interactions observed were several binding sites for proteins with repressor activity, including YY1, CCAAT displacement protein, and G1/G2 complexes (uncharacterized putative repressors) and several binding sites for the stage selector protein. To complement this analysis, orthologous galago sequences were also used to derive probes and the pattern of proteins binding to human and galago probes was compared. Binding interactions differing between these two species could be responsible for the different expression patterns shown by the two γ genes (galago γ is embryonic; human γ is fetal). Alternatively, binding interactions that are conserved in the two species may be important in the regulation of common expression patterns (eg, repression of γ in adult life).

Abstract: Given a sequenceA and regular expressionR, theapproximate regular expression matching problem is to find a sequence matchingR whose optimal alignment withA is the highest scoring of all such sequences. This paper develops an algorithm to solve the problem in timeO(MN), whereM andN are the lengths ofA andR. Thus, the time requirement is asymptotically no worse than for the simpler problem of aligning two fixed sequences. Our method is superior to an earlier algorithm by Wagner and Seiferas in several ways. First, it treats real-valued costs, in addition to integer costs, with no loss of asymptotic efficiency. Second, it requires onlyO(N) space to deliver just the score of the best alignment. Finally, its structure permits implementation techniques that make it extremely fast in practice. We extend the method to accommodate gap penalties, as required for typical applications in molecular biology, and further refine it to search for substrings ofA that strongly align with a sequence inR, as required for typical data base searches. We also show how to deliver an optimal alignment betweenA andR in onlyO(N+logM) space usingO(MN logM) time. Finally, anO(MN(M+N)+N 2logN) time algorithm is presented for alignment scoring schemes where the cost of a gap is an arbitrary increasing function of its length.

Abstract: We consider efficient methods for computing a difference metric between two sequences of symbols, where the cost of an operation to insert or delete a block of symbols is a concave function of the block's length. Alternatively, sequences can be optimally aligned when gap penalties are a concave function of the gap length. Two algorithms based on the ‘candidate list paradigm’ first used by Waterman (1984) are presented. The first computes significantly more parsimonious candidate lists than Waterman's method. The second method refines the first to the point of guaranteeingO(N 2 lgN) worst-case time complexity, and under certain conditionsO(N 2). Experimental data show how various properties of the comparison problem affect the methods' relative performance. A number of extensions are discussed, among them a technique for constructing optimal alignments inO(N) space in expectation. This variation gives a practical method for comparing long amino sequences on a small computer.

Numerical stability is but one of many desirable properties which should be considered when designing statistical software. However, rigorous roundoff analysis is rarely done because it seems not worth the price; the influence of rounding error is usually of secondary importance, and the analysis is thought to be beyond the reach of all but a few specialists. This note discusses the role of roundoff analysis in the design of a statistical program and shows that new techniques sometimes make assessment of the effect of rounding errors no more difficult than the verification of other program properties.

The FASTA package of sequence comparison programs has been expanded to include FASTX and FASTY, which compare a DNA sequence to a protein sequence database, translating the DNA sequence in three frames and aligning the translated DNA sequence to each sequence in the protein database, allowing gaps and frameshifts. Also new are TFASTX and TFASTY, which compare a protein sequence to a DNA sequence database, translating each sequence in the DNA database in six frames and scoring alignments with gaps and frameshifts. FASTX and TFASTX allow only frameshifts between codons, while FASTY and TFASTY allow substitutions or frameshifts within a codon. We examined the performance of FASTX and FASTY using different gap-opening, gap-extension, frameshift, and nucleotide substitution penalties. In general, FASTX and FASTY perform equivalently when query sequences contain 0–10% errors. We also evaluated the statistical estimates reported by FASTX and FASTY. These estimates are quite accurate, except when an out-of-frame translation produces a low-complexity protein sequence. We used FASTX to scan theMycoplasma genitalium, Haemophilus influenzae,andMethanococcus jannaschiigenomes for unidentified or misidentified protein-coding genes. We found at least 9 new protein-coding genes in the three genomes and at least 35 genes with potentially incorrect boundaries.

Abstract: This paper presents a dynamic programming algorithm for aligning two sequeces when the alignment is constrained to lie between two arbitrary boundary lines in the dynamic programming matrix. For affine gap penalties, the algorithm requires onlyO(F) computation time andO(M+N) space, whereF is the area of the feasible region andM andN are the sequence lengths. The result extends to concave gap penalties, with somewhat increased time and space bounds.

The ε-globin genes of mammals are expressed in early embryos, but are silenced during fetal and adult erythropoiesis. As a guide to defining the regulatory elements involved in this developmental switch, we have searched the sequences of ε-globin genes from different mammals for highly conserved segments. The search was facilitated by the development of a new program, called yama, to generate a multiple alignment of very long sequences using an improved scoring scheme. This allowed us to generate a multiple alignment of sequences from a more divergent group than previously analyzed, as demonstrated here for representatives of four mammalian orders. In parallel experiments, we constructed a series of deletion mutations in the 5' flank of the rabbit ε-globin gene and tested their effect on an ε-globin-luciferase hybrid reporter gene. These results show that 121 bp of 5' flank, containing CACC, CCAAT and ATA motifs, is sufficient for expression in erythroid K562 cells. Both positive and negative cis-acting control sequences are located between 218 and 394 bp 5' to the cap site, in a region previously proposed to be a silencer. The positive regulatory sequence contains conserved binding sites for the nuclear protein YY1 adjacent to another highly conserved sequence. The negative element contains a conserved sequence followed by a purine-rich segment. This analysis maps the upstream control sequences more precisely and points to a very complex regulatory scheme for this gene.

File update programs, such as the UNIX make command are invaluable, but enigmatic. They are difficult to write because the repercussions of an algorithmic variation can be elusive. Even experienced users often specify file relationships incorrectly, and are occasionally suprised by the tool's behaviour. This paper develops a rigorous conceptual model and employs it to answer some of the questions facing writers and users of file update tools. Coupled with empirical data about makefiles, these results motivate a conceptually simple update program.

Summary Many procedures, for example Gaussian elimination with partial pivoting, have been shown to be stable in the following sense. The effect of round-off errors is to produce a computed solution which is the exact solution for slightly different data. Sometimes that is equivalent to the computed solution being close to the exact solution. In this paper we study this equivalence.

The size of the error incurred by one operation in an interval arithmetic procedure depends on the extent to which the operands are dependent, i.e., depend on the same initial variables. In this part we will investigate the effect of such dependence. Our results are applied to prove the quadratic convergence of the “centered form” and of a method of Hansen and Smith for solving linear algebraic systems.

Several procedures in interval arithmetic have been shown to have errorO(w2), wherew is the width of the data intervals. In this paper we will give a general discussion of this “quadratic convergence”. Our results will allow us to give some systematic proofs of quadratic convergence.

Hansen and Smith have proposed a method for solving linear algebraic systems with interval coefficients which produces good results if the intervals are narrow. In this paper we show that the error of their method isO(W2), whereW is the width of the set of coefficients. The effects of round-off errors are not considered.

Necessary and sufficient conditions are given for “quadratic convergence” in interval arithmetic.

It is well-known that Gaussian elimination is very sensitive to round-off errors if row interchanges are not performed. In this note we make precise and prove the fact that there exist sets of data for which that algorithm leads to improper results regardless of how many digits are carried in the computation.

This unit focuses on some of the tools available on the public Galaxy server that are useful for exploring possible associations between human genetic variants and phenotypes. We trace step‐by‐step through an example illustrating several methods for examining a single full‐coverage genome to look for single‐nucleotide polymorphisms (SNPs) that are either known to be associated with disease or suspected to have impact for other reasons. It makes use of public genomic data, tools designed specifically for working with variants, and also some general tools for text manipulation and operations on genomic coordinates. Curr. Protoc. Bioinform. 39:15.2.1‐15.2.27. © 2012 by John Wiley & Sons, Inc.

The MultiPipMaker World Wide Web server (http://www.bx.psu.edu) provides a tool for aligning multiple DNA sequences and visualizing regions of conservation among them. This unit describes its use and gives an explanation of the resulting output files and supporting tools. Features provided by the server include alignment of up to 20 very long genomic sequences, output choices of a true, nucleotide‐level multiple alignment and/or stacked, pairwise percent identity plots, and support for user‐specified annotations of genomic features and arbitrary regions, with clickable links to additional information. Input sequences other than the reference can be fragmented, unordered, and unoriented. Curr. Protoc. Bioinform. 30:10.4.1‐10.4.14. © 2010 by John Wiley & Sons, Inc.

Background The evolutionary distance between human and macaque is particularly attractive for investigating local variation in neutral substitution rates, because substitutions can be inferred more reliably than in comparisons with rodents and are less influenced by the effects of current and ancient diversity than in comparisons with closer primates. Here we investigate the human-macaque neutral substitution rate as a function of a number of genomic parameters.Results Using regression analyses we find that male mutation bias, male (but not female) recombination rate, distance to telomeres and substitution rates computed from orthologous regions in mouse-rat and dog-cow comparisons are prominent predictors of the neutral rate. Additionally, we demonstrate that the previously observed biphasic relationship between neutral rate and GC content can be accounted for by properly combining rates at CpG and non-CpG sites. Finally, we find the neutral rate to be negatively correlated with the densities of several classes of computationally predicted functional elements, and less so with the densities of certain classes of experimentally verified functional elements.Conclusion Our results suggest that while female recombination may be mainly responsible for driving evolution in GC content, male recombination may be mutagenic, and that other mutagenic mechanisms acting near telomeres, and mechanisms whose effects are shared across mammalian genomes, play significant roles. We also have evidence that the nonlinear increase in rates at high GC levels may be largely due to hyper-mutability of CpG dinucleotides. Finally, our results suggest that the performance of conservation-based prediction methods can be improved by accounting for neutral rates.

Background Gene regulation is considered one of the driving forces of evolution. Although protein-coding DNA sequences and RNA genes have been subject to recent evolutionary events in the human lineage, it has been hypothesized that the large phenotypic divergence between humans and chimpanzees has been driven mainly by changes in gene regulation rather than altered protein-coding gene sequences. Comparative analysis of vertebrate genomes has revealed an abundance of evolutionarily conserved but noncoding sequences. These conserved noncoding (CNC) sequences may well harbor critical regulatory variants that have driven recent human evolution.Results Here we identify 1,356 CNC sequences that appear to have undergone dramatic human-specific changes in selective pressures, at least 15% of which have substitution rates significantly above that expected under neutrality. The 1,356 'accelerated CNC' (ANC) sequences are enriched in recent segmental duplications, suggesting a recent change in selective constraint following duplication. In addition, single nucleotide polymorphisms within ANC sequences have a significant excess of high frequency derived alleles and high FSTvalues relative to controls, indicating that acceleration and positive selection are recent in human populations. Finally, a significant number of single nucleotide polymorphisms within ANC sequences are associated with changes in gene expression. The probability of variation in an ANC sequence being associated with a gene expression phenotype is fivefold higher than variation in a control CNC sequence.Conclusion Our analysis suggests that ANC sequences have until very recently played a role in human evolution, potentially through lineage-specific changes in gene regulation.

The MultiPipMaker World Wide Web server (http://www.bx.psu.edu) provides a useful tool for aligning multiple sequences and visualizing regions of conservation between them. This unit describes the use of the MultiPipMaker server and gives an explanation of the resulting output files and supporting tools. Features provided by the server include alignment of up to 20 very long genomic sequences, output choices of a true, nucleotide‐level multiple alignment or stacked, pairwise percent identity plots, and user‐specified annotations for genomic features and elements of choice, with clickable links to additional information. Alignments can include unordered, unoriented secondary sequences.

Motivation: The gene expression intensity information conveyed by (EST) Expressed Sequence Tag data can be used to infer important cDNA library properties, such as gene number and expression patterns. However, EST clustering errors, which often lead to greatly inflated estimates of obtained unique genes, have become a major obstacle in the analyses. The EST clustering error structure, the relationship between clustering error and clustering criteria, and possible error correction methods need to be systematically investigated. Results: We identify and quantify two types of EST clustering error, namely, Type I and II in EST clustering using CAP3 assembling program. A Type I error occurs when ESTs from the same gene do not form a cluster whereas a Type II error occurs when ESTs from distinct genes are falsely clustered together. While the Type II error rate is <1.5% for both 5′ and 3′ EST clustering, the Type I error in the 5′ EST case is ∼10 times higher than the 3′ EST case (30% versus 3%). An over-stringent identity rule, e.g., P ≥ 95%, may even inflate the Type I error in both cases. We demonstrate that ∼80% of the Type I error is due to insufficient overlap among sibling ESTs (ISO error) in 5′ EST clustering. A novel statistical approach is proposed to correct ISO error to provide more accurate estimates of the true gene cluster profile. Availability: We have automated the methods developed in this paper in a web-based software ESTstat at http://cwdg5.bio.psu.edu/eststat. Supplementary information: http://cwdg5.bio.psu.edu/eststat

PipMaker is a World-Wide Web site used to compare two long genomic sequences and identify conserved segments between them. This unit describes the use of the PipMaker server and explains the resulting output files. PipMaker provides an efficient method of aligning genomic sequences and returns a compact, but easy-to-interpret form of output, the percent identity plot (pip). For each aligning segment between two sequences the pip shows both the position relative to the first sequence and the degree of similarity. Optional annotations on the pip provide additional information to assist in the interpretation of the alignment. The default parameters of the underlying blastz alignment program are tuned for human-mouse alignments.

Methods are presented for organizing and integrating DNA sequence data, restriction maps, and genetic maps for the same organism but from a variety of sources (databases, publications, personal communications). Proper software tools are essential for successful organization of such diverse data into an ordered, cohesive body of information, and a suite of novel software to support this endeavor is described. Though these tools automate much of the task, a variety of strategies is needed to cope with recalcitrant cases. We describe such strategies and illustrate their application with numerous examples. These strategies have allowed us to order, analyze, and display over one megabase of E. coli DNA sequence information. The integration task often exposes inconsistencies In the available data, perhaps caused by strain polymorphisms or human oversight, necessitating the application of sound biological judgment. The examples illustrate both the level of expertise required of the database curator and the knowledge gained as apparent inconsistencies are resolved. The software and mapping methods are applicable to the study of any genome for which a high resolution restriction map is available. They were developed to support a weakly coordinated sequencing effort involving many laboratories, but would also be useful for highly orchestrated sequencing projects.

Space, not time, is often the limiting factor when computing optimal sequence alignments, and a number of recent papers in the biology literature have proposed space-saving strategies. However, a 1975 computer science paper by Hirschberg presented a method that is superior to the new proposals, both in theory and in practice. The goal of this paper is to give Hirschberg's idea the visibility it deserves by developing a linear-space version of Gotoh's algorithm, which accommodates affine gap penalties. A portable C-software package implementing this algorithm is available on the BIONET free of charge.

This paper presents an algorithm thai searches a DNA restriction enzyme map for regions that approximately match a shorter 'probe' map. Both the map and the probe consist of a sequence of address-enzyme pairs denoting restriction sites, and the algorithm penalizes a potential match for undetected or missing sites and for discrepancies in the distance between adjacent sites. The algorithm was designed specifically for comparing relatively short DNA sequences with a long restriction map, a problem that will become increasing common as large physical maps are generated. The algorithm has been used to extract information from a restriction map of the entire Escherichia coli genome.

Existing dynamic-programming algorithms for identifying similar regions of two sequences require time and space proportional to the product of the sequence lengths. Often this space requirement is more limiting than the time requirement. We describe a dynamic-programming local-similarity algorithm that needs only space proportional to the sum of the sequence lengths. The method can also find repeats within a single long sequence. To illustrate the algorithm's potential, we discuss comparison of a 73 360 nucleotide sequence containing the human β-like globin gene cluster and a corresponding 44 594 nucleotide sequence for rabbit, a problem well beyond the capabilities of other dynamic-programming software.

This paper presents a practical program, called sim2, for building local alignments of two sequences, each of which may be hundreds of kilobases long. sim2 first constructs n best non-intersecting chains of ‘fragments’, such as all occurrences of identical 5-tuples in each of two DNA sequences,for any specified n ≥ 1. Each chain is then refined by delivering an optimal alignment in a region delimited by the chain. sim2 requires only space proportional to the size of the input sequences and the output alignments, and the same source code runs on Unix machines, on Macintoshes, on PCs, and on DEC Alpha PCs. We also describe an application of sim2 for aligning long DNA sequences from Escherichia coli. sim2 facilitates contig-building by providing a complete view of the related sequences, so difference can be analyzed and inconsistencies resolved. Examples are shown using the alignment display and editing functions from the software tool ChromoScope.