Search PubMed⌕ Search

Biomedical subjects

P A Pevzner

Publications and source records attributed to P A Pevzner.

36 records · Page 2Linked to original sources
PubMed1997

Software for DNA sequencing by hybridization.

Sequencing by hybridization (SBH) is a promising alternative approach to DNA sequencing and mutation detection. Analysis of the resolving power of SBH involves rather difficult combinatorial and probabilistic problems, and sometimes computer simulation is the only way to estimate the parameters and limitations of SBH experiments. This paper describes a software package, DNA-SPECTRUM, which allows one to analyze the resolving power and parameters of SBH. We also introduce the technique for visualizing multiple SBH reconstructions and describe applications of DNA-SPECTRUM to estimate various SBH parameters. DNA-SPECTRUM is available at http://www-hto.usc.edu/software/sbh/index. html.

Base Sequence↗
PubMed1996

Gene recognition via spliced sequence alignment.

Gene recognition is one of the most important problems in computational molecular biology. Previous attempts to solve this problem were based on statistics, and applications of combinatorial methods for gene recognition were almost unexplored. Recent advances in large-scale cDNA sequencing open a way toward a new approach to gene recognition that uses previously sequenced genes as a clue for recognition of newly sequenced genes. This paper describes a spliced alignment algorithm and software tool that explores all possible exon assemblies in polynomial time and finds the multiexon structure with the best fit to a related protein. Unlike other existing methods, the algorithm successfully recognizes genes even in the case of short exons or exons with unusual codon usage; we also report correct assemblies for genes with more than 10 exons. On a test sample of human genes with known mammalian relatives, the average correlation between the predicted and actual proteins was 99%. The algorithm correctly reconstructed 87% of genes and the rare discrepancies between the predicted and real exon-intron structures were caused either by short (less than 5 amino acids) initial/terminal exons or by alternative splicing. Moreover, the algorithm predicts human genes reasonably well when the homologous protein is nonvertebrate or even prokaryotic. The surprisingly good performance of the method was confirmed by extensive simulations: in particular, with target proteins at 160 accepted point mutations (PAM) (25% similarity), the correlation between the predicted and actual genes was still as high as 95%.

Algorithms↗
PubMed1996

Positional sequencing by hybridization.

Sequencing by hybridization (SBH) is a promising alternative to the classical DNA sequencing approaches. However, the resolving power of SBH is rather low: with 64kb sequencing chips, unknown DNA fragments only as long as 200 bp can be reconstructed in a single SBH experiment. To improve the resolving power of SBH, positional SBH (PSBH) has recently been suggested; this allows (with additional experimental work) approximate positions of every l-tuple in a target DNA fragment to be measured. We study the positional Eulerian path problem motivated by PSBH. The input to the positional eulerian path problem is an Eulerian graph G(V, E) in which every edge has an associated range of integers and the problem is to find an Eulerian path e1,...,e/E/ in G such that the range of ei contains i. We show that the positional Eulerian path problem is NP-complete even when the maximum out-degree (in-degree) of any vertex in the graph is 2. On a positive note we present polynomial algorithms to solve a special case of PSBH (bounded PSBH), where the range of the allowed positions for any edge is bounded by a constant (it corresponds to accurate experimental measurements of positions in PSBH). Moreover, if the positions of every l-tuple in an unknown DNA fragment of length n are measured with O(log n) error, then our algorithm runs in polynomial time. We also present an estimate of the resolving power of PSBH for a more realistic case when positions are measured with theta (n) error.

Algorithms↗
PubMed1995

Genome sequence comparison and scenarios for gene rearrangements: a test case.

As large portions of related genomes are being sequenced, methods for comparing complete or nearly complete genomes, as opposed to comparing individual genes, are becoming progressively more important. A major, widespread phenomenon in genome evolution is the rearrangement of genes and gene blocks. There is, however, no consistent method for genome sequence comparison combined with the reconstruction of the evolutionary history of highly rearranged genomes. We developed a schema for genome sequence comparison that includes three successive steps: (i) comparison of all proteins encoded in different genomes and generation of genomic similarity plots; (ii) construction of an alphabet of conserved genes and gene blocks; and (iii) generation of most parsimonious genome rearrangement scenarios. The approach is illustrated by a comparison of the herpesvirus genomes that constitute the largest set of relatively long, complete genome sequences available to date. Herpesviruses have from 70 to about 200 genes; comparison of the amino acid sequences encoded in these genes results in an alphabet of about 30 conserved genes comprising 7 conserved blocks that are rearranged in the genomes of different herpesviruses. Algorithms to analyze rearrangements of multiple genomes were developed and applied to the derivation of most parsimonious scenarios of herpesvirus evolution under different evolutionary models. The developed approaches to genome comparison will be applicable to the comparative analysis of bacterial and eukaryotic genomes as soon as their sequences become available.

DNA, Viral↗
PubMed1995

DNASUN: a package of computer programs for the biotechnology laboratory.

The paper describes a new software package DNASUN developed for supporting gene engineering laboratories. The package provides a user-friendly interface for experimental researches and supports the traditional nucleotide/protein sequence analysis as well as physical mapping, sequencing, plasmid manipulations, optimal oligonucleotide probe selection and other common molecular biology procedures.

Biotechnology↗
PubMed1994

Rearrangements of DNA sequences and SBH.

Despite recent advances in DNA sequencing by hybridization it is still a random shotgun method. Even if one manages to routinely sequence short DNA fragments by SBH these fragments have to be assembled into the final genomic sequence. Recently different additional biochemical experiments were suggested which potentially may drastically increase the resolving power of SBH. However biologists frequently cannot estimate the computer science limitations of the proposed additional experiments and no computational studies of additional experiments for SBH were provided yet. The paper discusses a combinatorial technique which might help a biologist to analyze different additional biochemical experiments and to combine these data with SBH data to increase the resolving power of SBH.

Base Sequence↗
PubMed1992

Statistical distance between texts and filtration methods in sequence comparison.

Upon searching local similarities in long sequences, the necessity of a 'rapid' similarity search becomes acute. Quadratic complexity of dynamic programming algorithms forces the employment of filtration methods that allow elimination of the sequences with a low similarity level. The paper is devoted to the theoretical substantiations of the filtration method based on the statistical distance between texts. The notion of the filtration efficiency is introduced and the efficiency of several filters is estimated. It is shown that the efficiency of the statistical l-tuple filtration upon DNA database search is associated with a potential extension of the original four-letter alphabet and grows exponentially with increasing l. The formula that allows one to estimate the filtration parameters is presented.

Amino Acid Sequence↗
PubMed1992

Extendable words in nucleotide sequences.

Previous statistical analyses revealed several peculiarities of nucleotide sequences that preclude their description by existing models and thus allow one to distinguish DNA and RNA sequences from random A,T,G,C-texts. This is a consequence of the unusual distribution of certain words in nucleotide sequences: while the distribution of (most) words is consistent with Markov models of small orders, the distribution of certain words cannot be described by any previous model (anomalies in distribution of homonucleotide/homopurine/homopyrimidine runs, complementary and mirror palindromes, and non-stationary words). In this work we introduce a probabilistic approach that is partly motivated by analogy with linguistics. We also describe another important feature of DNA/RNA sequences: anomalies in distribution of words of poor nucleotide composition. We show that some classes of these words are the major obstacle for the simple Markov description of nucleotide sequences.

Base Sequence↗
PubMed1991

Improved chips for sequencing by hybridization.

The SHOM method (Sequencing by Hybridization with Oligonucleotide Matrix) developed in 1988 is a new approach to nucleic acid sequencing by hybridization to an oligonucleotide matrix composed of an array of immobilized oligonucleotides. The original matrix proposed for sequencing by SHOM had to contain at least 65,536 octanucleotides. The present work describes a new family of matrices, which allows one to reduce the number of synthesized oligonucleotides 5-15 times without essentially decreasing the resolving power of the method.

Algorithms↗
PubMed1991

Genome inhomogeneity is determined mainly by WW and SS dinucleotides.

According to the hypothesis of the modular structure of DNA, genomes consist of modules of various nature which may differ in statistical characteristics. Statistical analysis helps in revealing the differences in statistical characteristics and predicting the modular structure. In this connection the question about the contribution of each word of length l (l-tuple) to the inhomogeneity of genetic text arises. The notion of stationary (i.e. relatively evenly distributed over a genome) versus non-stationary l-tuples has been introduced previously. In this paper, the dinucleotide distributions for all long sequences from GenBank were analyzed and it was shown that non-stationary dinucleotides are closely associated with polyW and polyS tracts (W denotes 'weak' nucleotides A or T, while S stands for the 'strong' nucleotides G or C). Thus, genome inhomogeneity is shown to be determined mainly by AA, TT, GG, CC, AT, TA, GC and CG dinucleotides. It has been demonstrated that neither 'codon usage' nor the 'isochore model' can account for this phenomenon.

Algorithms↗
PubMed1989

Linguistics of nucleotide sequences. I: The significance of deviations from mean statistical characteristics and prediction of the frequencies of occurrence of words.

Mathematical models of the generation of genetic texts appeared simultaneously with the first sequencing DNA. They are used to establish functional and evolutionary relations between genetic texts, to predict the number and distribution of specific sites in a sequence and to identify "meaningful" words. The present paper deals with two problems: 1) The significance of deviations from the mean statistical characteristics in a genetic text. Anyone who has addressed himself to the statistical analysis of sequenced DNA is familiar with the question: what deviations from the expected frequencies of occurrence of particular words testify to the "biological" significance of those words? We propose a formula for the variance of the number of word's occurrences in the text, with allowance for word overlaps, making it possible to assess the significance of the deviations from the expected statistical characteristics. 2) A new method for predicting the frequencies of occurrence of particular words in a genetic text using the statistical characteristics of "spaced" L-grams. The method can be used for predicting the number of restriction sites in human DNA and in planning experiments on the physical mapping and sequencing of the human genome.

Bacteriophage lambda↗
PubMed1989

Linguistics of nucleotide sequences. II: Stationary words in genetic texts and the zonal structure of DNA.

Words are irregularly distributed in genetic texts. The analysis of this irregularity leads to the notion of stationary and non-stationary words. The polyW and polyS tracts are shown to be the most non-stationary words in genetic texts (here W-[A,T], S-[G,C], a polyW tract is a sequence of A,T nucleotides and a polyS tract is a sequence of G,C nucleotides. The distribution of stationary words suggests a method for partitioning DNA into zones. The zones obtained in the case of the phage are interpreted in the light of the Dowe hypothesis of the modular structure of bacteriophage genomes.

Adenoviridae↗
PubMed1989

1-Tuple DNA sequencing: computer analysis.

A new method of DNA reading was proposed at the end of 1988 by Lysov et al. According to the authors' claims it has certain advantages as compared to the Maxam-Gilbert and Sanger methods, which are revealed by automation and rapidity of DNA sequencing. Nevertheless its employment is hampered by a number of biological and mathematical problems. The present study proposes an algorithm that allows to overcome the computational difficulties occurring in the course of the method during reconstruction of the DNA sequence by its l-tuple composition. It is shown also that the biochemical problems connected with the loss of information about the l-tuple DNA composition during hybridization are not crucial and can be overcome by finding the maximal flow of minimal cost in the special graph.

Algorithms↗
PubMedDate not supplied

De novo peptide sequencing via tandem mass spectrometry.

Peptide sequencing via tandem mass spectrometry (MS/MS) is one of the most powerful tools in proteomics for identifying proteins. Because complete genome sequences are accumulating rapidly, the recent trend in interpretation of MS/MS spectra has been database search. However, de novo MS/MS spectral interpretation remains an open problem typically involving manual interpretation by expert mass spectrometrists. We have developed a new algorithm, SHERENGA, for de novo interpretation that automatically learns fragment ion types and intensity thresholds from a collection of test spectra generated from any type of mass spectrometer. The test data are used to construct optimal path scoring in the graph representations of MS/MS spectra. A ranked list of high scoring paths corresponds to potential peptide sequences. SHERENGA is most useful for interpreting sequences of peptides resulting from unknown proteins and for validating the results of database search algorithms in fully automated, high-throughput peptide sequencing.

Algorithms↗
PubMedDate not supplied

[Optimal chips for megabase DNA sequencing].

The SHOM method (Sequencing by Hybridization with Oligonucleotide Matrix) developed in 1988 is a new approach to nucleic acid sequencing by hybridization to a octanucleotide matrix composed of an array of immobilized oligonucleotides. The original matrix proposed for sequencing by SHOM had to contain at least 65,536 octanucleotides. The present work describes a new family of matrices for sequencing, which allows one to reduce the number of synthesized oligonucleotides 5-15 times without essentially decreasing the resolving power of the method.

Base Sequence↗
PubMedDate not supplied

[Paths in graphs and selection of oligonucleotide linkers].

The problem of search of an universal linker with minimal length containing all restriction endonuclease recognition sites is considered. We reduce this problem to the search of Eiler's and Hamilton's paths in graph. The use of the discrete optimization methods allows to construct the linker with the length closed to the minimum.

Base Sequence↗
PubMedDate not supplied

[Effective method for physical mapping the DNA molecule].

The method of DNA molecules physical mapping based on the algorithms of discrete optimization and graph theory was proposed. The input information consisted of the sizes of single and double restrictions fragments and the level of their measurement errors. The method presents possibilities for optimal planning of experiments and step by step construction of physical maps. Efficiency of the method and examples of its application are discussed.

DNA↗