Search PubMed⌕ Search

Biomedical subjects

D Sankoff

Publications and source records attributed to D Sankoff.

At least 37 records · Page 2Linked to original sources
PubMed1996

Parametric genome rearrangement.

Algorithms inspired by comparative genomics calculate an edit distance between two linear orders based on elementary edit operations such as inversion, transposition and reciprocal translocation. All operations are generally assigned the same weight, simply by default, because no systematic empirical studies exist verifying whether algorithmic outputs involve realistic proportion of each. Nor do we have data on how weights should vary with the length of the inverted or transposed segment of the chromosome. In this paper, we present a rapid algorithm that allows each operation to take on a range of weights, producing an relatively tight upper bound on the distance between single-chromosome genomes, by means of a greedy search with look-ahead. The efficiency of this algorithm allows us to test random genomes for each parameter setting, to detect gene order similarity and to infer the parameter values most appropriate to the phylogenetic domain under study. We apply this method to genome segments in which the same gene order is conserved in Escherichia coli and Bacillus subtilis, as well as to the gene order in human versus Drosophila mitochondrial genomes. In both cases, we conclude that it is most appropriate to assign somewhat more than twice the weight to transpositions and inverted transpositions than to inversions. We also explore segment-length weighting for fungal mitochondrial gene orders.

Algorithms↗
PubMed1996

Evolution of fragmented mitochondrial ribosomal RNA genes in Chlamydomonas.

The fragmented mitochondrial ribosomal RNAs (rRNAs) of the green algae Chlamydomonas eugametos and Chlamydomonas reinhardtii are discontinuously encoded in subgenic modules that are scrambled in order and interspersed with protein coding and tRNA genes. The mitochondrial rRNA genes of these two algae differ, however, in both the distribution and organization of rRNA coding information within their respective genomes. The objectives of this study were (1) to examine the phylogenetic relationships between the mitochondrial rRNA gene sequences of C. eugametos and C. reinhardtii and those of the conventional mitochondrial rRNA genes of the green alga, Prototheca wickerhamii, and land plants and (2) to attempt to deduce the evolutionary pathways that gave rise to the unusual mitochondrial rRNA gene structures in the genus Chlamydomonas. Although phylogenetic analysis revealed an affiliation between the mitochondrial rRNA gene sequences of the two Chlamydomonas taxa to the exclusion of all other mitochondrial rRNA gene sequences tested, no specific affiliation was noted between the Chlamydomonas sequences and P. wickerhamii or land plants. Calculations of the minimal number of transpositions required to convert hypothetical ancestral rRNA gene organizations to the arrangements observed for C. eugametos and C. reinhardtii mitochondrial rRNA genes, as well as a limited survey of the size of mitochondrial rRNAs in other members of the genus, lead us to propose that the last common ancestor of Chlamydomonas algae contained fragmented mitochondrial rRNA genes that were nearly co-linear with conventional rRNA genes.

Animals↗
PubMed1996

A remarkable nonlinear invariant for evolution with heterogeneous rates.

A model for DNA or protein sequence evolution is proposed where each position belongs to one of two distinct classes. The two classes evolve at different rates. For a phylogeny on four species, we find a cubic function of 4-tuple occurrence frequencies that is nontrivially invariant no matter what the proportion of positions in each rate class. This result refutes the major criticism of nonlinear polynomial invariants.

DNA↗
PubMed1996

Karyotype distributions in a stochastic model of reciprocal translocation.

A random process of reciprocal translocation for a fixed number k of chromosomes (or arms) will have an equilibrium distribution of chromosome lengths. In this paper we calculate this distribution, by analytical means for k = 2 and partially for k = 3, and simulate the means of the marginal distributions for higher k. We compare this with a random (i.e., ahistorical) distribution of genomic DNA among k chromosomes and to a selection of karyotypes of real organisms. The results motivate a revised model where translocations giving rise to undersize chromosomes are disadvantaged.

Karyotyping↗
PubMed1995

Phylogenetic invariants for more general evolutionary models.

An invariant Q of a tree T under a k-state Markov model, where a generalized time parameter is identified with the E edges of T, allows us to recognize whether data on N observed species (usually, N DNA sequences, one from each species) can be associated with the N leaves of T in the sense of having been generated on T rather than on any other N-leaf tree. The form of the generalized time parameter is a positive determinant matrix in some semigroup S of Markov matrices. The invariance is with respect to the choice of the set of E matrices in S, one associated with each of the E edges of T. The parametric form of S represents a model of the evolutionary process. In this paper, we apply a general method of finding invariants of a parametrized functional form to find low-degree polynomial invariants for different models. Quadratic invariants are obtained for the Kimura two-parameter model, for a model allowing evolutionary dependence between positions in the sequences and for an asymmetric model that allows for A + T versus G + C asymmetries in DNA base composition. Those invariants are found for trees (unrooted in case of the Kimura model and rooted for the others) with N = 3 or N = 4 terminal vertices. We also find cubic invariants for a ten-parameter model with k = 4 states, for rooted trees with N = 4. In each case, we use implicit function theory to predict the number of algebraically independent invariants and then use this prediction to guide a systematic search for algebraic dependence within the set of invariants produced by our method.

Animals↗
PubMed1994

Skewed base compositions, asymmetric transition matrices, and phylogenetic invariants.

Evolutionary inference methods that assume equal DNA base compositions and symmetric nucleotide substitution matrices, where these assumptions do not hold, are likely to group species on the basis of similar base compositions rather than true phylogenetic relationships. We propose an invariants-based method for dealing with this problem. An invariant QT of a tree T under a k-state Markov model, where a generalized time parameter is identified with the E edges of T, allows us to recognize whether data on N observed species can be associated with the N terminal vertices of T in the sense of having been generated on T rather than on any other tree with N terminals. The form of the generalized time parameter is a positive determinant matrix in some semigroup S of stochastic matrices. The invariance is with respect to the choice of the set of E matrices in S, one associated with each of the E edges of T. We apply a general "empirical" method of finding invariants of a parametrized functional form. It involves calculating the probability f of all KN data possibilities for each of m sets of E matrices in S to associate with the edges of T, then solving for the parameters using the m equations of form Q(f) = 0. We discuss the problems of finding asymmetric models satisfying the property of semigroup closure, of finding asymmetric models that admit invariants at all, and of the computational complexity of the method. We propose a class of semigroups Sc containing matrices of form [formula: see text] to account for A+T versus G+C asymmetries in DNA base composition. Quadratic invariants are obtained for rooted trees with three and with four terminals. In the latter case the smallest set of algebraically independent invariants is sought. These invariants are applied to data pertaining the fungal evolution and to the origin of mitochondria as bacterial endosymbionts.

Algorithms↗
PubMed1993

Analytical approaches to genomic evolution.

We model the non-local mechanisms of genomic evolution and propose methods for studying the evolutionary divergence of species based on these models. Mechanisms include the movement of segments of genomes within a single chromosome (transpositions), the reciprocal translocation of segments between two chromosomes, and the inversion of segments. Each of these is studied in the context of a different type of genomic data. We introduce the theory of phylogenetic invariants for evolutionary inference based on very long macromolecular sequences.

Animals↗
PubMed1992

Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome.

Detailed knowledge of gene maps or even complete nucleotide sequences for small genomes leads to the feasibility of evolutionary inference based on the macrostructure of entire genomes, rather than on the traditional comparison of homologous versions of a single gene in different organisms. The mathematical modeling of evolution at the genomic level, however, and the associated inferential apparatus are qualitatively different from the usual sequence comparison theory developed to study evolution at the level of individual gene sequences. We describe the construction of a database of 16 mitochondrial gene orders from fungi and other eukaryotes by using complete or nearly complete genomic sequences; propose a measure of gene order rearrangement based on the minimal set of chromosomal inversions, transpositions, insertions, and deletions necessary to convert the order in one genome to that of the other; report on algorithm design and the development of the DERANGE software for the calculation of this measure; and present the results of analyzing the mitochondrial data with the aid of this tool.

Biological Evolution↗
PubMed1992

Efficient optimal decomposition of a sequence into disjoint regions, each matched to some template in an inventory.

Given an amino acid sequence, we discuss how to find efficiently an optimal set of disjoint regions (substrings, domains, modules, etc.), each of which can be matched to some element of a predefined inventory containing, for example, consensus sequences, protosequences, or protein family profiles. A two-stage approach to sequence decomposition, consisting of the detection of all acceptable matches followed by the construction of an optimal subset of compatible matches, leads to computational difficulties. When the problem is reformulated in terms of network comparisons, it can be solved in time quadratic in the length of the sequence and linear with the number of templates in the inventory, by a single pass of a dynamic programming algorithm. This method has the advantage that the criterion for acceptable matches can be relaxed without materially affecting computing time. Except under special conditions it is more efficient than previous segmentation methods based on dynamic programming.

Algorithms↗
PubMed1990

Designer invariants for large phylogenies.

The Cavender-Felsenstein edge-length invariants for binary characters on 4-trees provide the starting point for the development of "customized" invariants for evaluating and comparing phylogenetic hypotheses. The binary character invariants may be generalized to k-valued characters without losing the quadratic nature of the invariants as functions of the theoretical frequencies f(UVXY) of observable character configurations (U at organism 1, V at 2, etc.). The key to the approach is that certain sets of these configurations constitute events which are probabilistically independent from other such sets, under the symmetric Markov change models studied. By introducing more complex sets of configurations, we find the quadratic invariants for 5-trees in the binary model and for individual edges in 6-trees or, indeed, in any size tree. The same technique allows us to formulate invariants for entire trees, but these are cubic functions for 6-trees and are higher-degree polynomials for larger trees. With k-valued characters and, especially, with large trees, the types of configuration sets (events) used in the simpler examples are too rare (i.e., their predicted frequencies are too low) to be useful, and the construction of meaningful pairs of independent events becomes an important and nontrivial task in designing invariants suited to testing specific hypotheses. In a very natural way, this approach fits in with well-known statistical methodology for contingency tables. We explore use of events such as "only transitions occur for character i (i.e., position i in a nucleic acid sequence) in subtree a" in analyzing a set of data on ribosomal RNA in the context of the controversy over the origins of archaebacteria, eubacteria, and eukaryotes.

Archaea↗
PubMed1989

Probabilistic models of genome shuffling.

The comparison of entire genomes in evolutionary studies gives rise to alignments characterized by many intersections, or inversions in the order of two fragments in different genomes. To model this, we suggest a random migration process for fragments, and discuss its equilibrium distribution in the case of linear and circular genomes. Simulations are carried out to explore "cut-off" behavior as the process approaches equilibrium. We define a new process to take into account the indistinguishability of two fragments which are adjacent in both genomes being compared. Questions of applicability of these models are discussed.

Biological Evolution↗
PubMed1989

A continuous analog for RNA folding.

A linear segment in which a number of pairs of intervals of equal length are identified as potential stems is the subject of a folding problem analogous to inference of RNA secondary structure. A quantity of free energy (or equivalently, energy per unit length) is associated with each stem, and the various types of loops are assigned energy costs as a function of their lengths. Inference of stable structures can then be carried out in the same way as in RNA folding. More important, perturbation of stem lengths and energy densities (modelling various mutational processes affecting nucleotide sequences) allows the delineation of domains of stability of various foldings, through the explicit calculation of their boundaries, in a low-dimensional parameter space.

Mathematics↗
PubMed1989

On the evolutionary origin of the plant mitochondrion and its genome.

Higher plants occupy very different positions in the mitochondrial and nuclear lineages of global phylogenetic trees based on conserved regions of small subunit (SSU) and large subunit (LSU) rRNA sequences. In the nuclear subtree, plants branch off late, at a position reflecting a massive radiation of the major multicellular (and some unicellular) groups; in the mitochondrial subtree, in contrast, plants branch off early, near the point of connection between the mitochondrial and eubacterial lineages. Moreover, in the nuclear lineage, plants branch together with the unicellular green alga Chlamydomonas reinhardtii, whereas in the mitochondrial lineage (in both SSU and LSU trees), metaphytes and chlorophyte branch separately. Statistical evaluation indicates that the anomalous branching position of higher plants in the mitochondrial lineage is not a treeing artifact attributable to the relatively rapid rate of sequence divergence of non-plant mitochondrial rRNA sequences. In considering alternative biological explanations for these results, we are led to propose that the rRNA genes in plant mitochondria may be of more recent evolutionary origin than the rRNA genes in other mitochondria. This proposal has implications for monophyletic vs. polyphyletic scenarios of mitochondrial origin and is consistent with other evidence indicating that plant mtDNA is an evolutionary mosaic.

Journal Article↗
PubMed1987

Computational complexity of inferring phylogenies from chromosome inversion data.

In systematics, parsimony methods construct phylogenies, or evolutionary trees, in which characters evolve with the least evolutionary change. The chromosome inversion, or polymorphism, parsimony criterion is used when each character of a population may exhibit homozygous or heterozygous states, but when the heterozygous state must evolve uniquely. Variations of the criterion concern whether or not the ancestral states of characters are specified. We establish that problems of inferring phylogenies by these criteria are NP-complete and thus are so difficult computationally that efficient optimal algorithms for them are unlikely to exist.

Algorithms↗
PubMed1987

Archetypical features in tRNA families.

A compilation of known tRNA, and tRNA gene sequences from archaebacteria, eubacteria, and eukaryotes permits the construction of tRNA cloverleafs which show conserved structural elements for each tRNA family. Positions conserved across the three kingdoms are thought to represent archetypical features of tRNAs which preceded the divergence of these kingdoms.

Archaea↗
PubMed1986

Allele and locus classification in electrophoretic population studies.

The electrophoretic separation of protein variants having slightly different mobilities is a basic tool of biochemical population genetics. In certain situations it is difficult to determine how to classify the variants as alleles of a number of genetic loci, that is, as variant subsets within each of which the Mendelian laws hold. In this article, we develop and analyze a series of algorithms for solving various versions and generalizations of this problem of optimal classification.

Alleles↗