The genome halving problem, previously solved by El-Mabrouk for inversions and reciprocal translocations, is here solved in a more general context allowing transpositions and block interchange as...
The where and wherefore of evolutionary breakpoints (2009)
Abstract The 'action' in genome-level evolution lies not in the large gene-containing segments that are conserved among related species, but in the breakpoint regions between these segments. Two...
Multichromosomal median and halving problems under different genomic distances (2009)
Tannier, Eric, Zheng, Chunfang, Sankoff, David
Abstract Background Genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor...
Genome aliquoting with double cut and join (2009)
Warren, Robert, Sankoff, David
Abstract Background The genome aliquoting probem is, given an observed genome A with n copies of each gene, presumed to descend from an n -way polyploidization event from an ordinary diploid genome B...
D: The Statistical Analysis of Spatially Clustered Geens under the Maximum Gap Criterion (2008)
Rose Hoberman, David Sankoff, Dannie Durand
Statistical validation of gene clusters is imperative for many important applications in comparative genomics which depend on the identification of genomic regions that are historically and/or...
Dissertation: A Statistical Framework for Spatial Comparative Genomics (2008)
Rose Hoberman, Advisor Dannie Durand, Committee Jeffrey Lawrence, Andrew Moore, David Sankoff, Russell Schwartz, ...
Thesis: A statistical framework for analyzing the spatial organization of genes within and across genomes. Applications include reconstruction of ancestral gene order, analysis
The Distribution of Inversion Lengths in Bacteria (2008)
David Sankoff, Jean-françois Lefebvre, Elisabeth Tillier, Adrian Maler, Nadia El-mabrouk
Abstract. The distribution of the lengths of genomic segments inverte during the evolutionary divergence of two species cannot be inferred d rectly from the output of genome rearrangement algorithms,...
REVIEW Structural Dynamics of Eukaryotic Chromosome Evolution (2008)
E. W. Brown, J. E. Leclerc, B. Li, W. L. Payne, S. J. Weissman, S. L. Moseley, ...
36. We thank H. Merkert for excellent graphical assistance
David Sankoff, Chungfang Zheng, Er Lenert
Abstract. The objective function of the genome rearrangement problems allows the integration of other genome-level problems so that they may be solved simultaneously. Three examples, all of which are...
David Sankoff, Chunfang Zheng, Qian Zhu
Motivation: Autopolyploidization and allopolyploidization events multiply the number of chromosomes and genomic content. Genome rearrangement phylogenetics requires that all genomes analyzed have the...
We review the combinatorial optimization problems in cal-culating edit distances between genomes and phylogenetic inference based on minimizing gene order changes. With a view to avoiding the...
Enjoy this Phylogenomics Conference! (2008)
Nadia El-mabrouk, Franz Lang, Vladimir Makarenkov, ...
This conference aims to bring together experts focusing on two distinct aspects of phylogenomics: the use of genome data to infer species phylogeny and the use of phylogenetic approaches to gain...
Polyploids, Genome Halving and Phylogeny (2008)
David Sankoff, Chunfang Zheng, Qian Zhu
Autopolyploidization and allopolyploidization events multiply the number of chromosomes and genomic content. Genome rearrangement phylogenetics requires that all genomes analyzed have the same set of...
1 Introduction. Conserved segment identification (2008)
David Sankoff, Vincent Ferretti, Joseph H. Nadeau
The study of genome rearrangements based on map dat,a depends crucially on the definition and identification of COIL-
The production of code-mixed discourse (2008)
We propose a comprehensive theory of code-mixed discourse, encompassing equivalence-point and insertional code-switching, palin-dromic constructions and lexical borrowing. The starting point is a...
BIOINFORMATICS Genome rearrangement with gene families (2008)
Motivation: The theory and practice of genome rearrangement analysis breaks down in the biologically widespread contexts where each gene may be present in a number of copies, not necessarily...
The ABCs of MGR with DCJ (2008)
We study the small phylogeny problem in the space of multichromosomal genomes under the double cut and join metric. This is similar to the existing MGR (multiple genome rearrangements) approach but...
Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes (2008)
Zheng, Chunfang, Zhu, Qian, Adam, Zaky, Sankoff, David
Motivation: Some present day species have incurred a whole genome doubling event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout...
The production of code-mixed discourse (2007)
We propose a comprehensive theory of code-mixed discourse, encompassing equivalence-point and insertional code-switching, palin-dromic constructions and lexical borrowing. The starting point is a...
DUPLICATION, REARRANGEMENT AND RECONCILIATON (2007)
David Sankoff, Nadia El-mabrouk
A method to account for gene order data from N genomes according to a given species tree, with no restriction on the number of approximate copies of a gene (or of members of a gene family) in a...
J Mol Evol (1999) 49:193–203 Gene Order Breakpoint Evidence in Animal Mitochondrial Phylogeny (2007)
Mathieu Blanchette, Takashi Kunisawa, David Sankoff
Abstract. Multiple genome rearrangement methodology facilitates the inference of animal phylogeny from gene orders on the mitochondrial genome. The breakpoint distance is preferable to other, highly...
D'epartement d'informatique et de recherche op'erationelle, Universit'e de Montr'eal, (2007)
Nadia El-mabrouk, David Sankoff, Qu'ebec Hc J
using minimum reversals
The method of phylogenetic invariants was developed to apply to aligned sequence data generated, according to a stochastic substitution model, for N species related through an unknown phylogenetic...
Polyploids, genome halving and phylogeny (2007)
Sankoff, David, Zheng, Chunfang, Zhu, Qian
Motivation: Autopolyploidization and allopolyploidization events multiply the number of chromosomes and genomic content. Genome rearrangement phylogenetics requires that all genomes analyzed have the...
Genome Halving with an Outgroup (2006)
Chunfang Zheng, Qian Zhu, David Sankoff
Some genomes are known to have incurred a genome doubling (tetraploidization) event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout...
Genome Halving with an Outgroup (2006)
Chunfang Zheng, Qian Zhu, David Sankoff
Some genomes are known to have incurred a genome doubling (tetraploidization) event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout...
D.: Genome halving with an outgroup (2006)
Chunfang Zheng, Qian Zhu, David Sankoff
Abstract: Some genomes are known to have incurred a genome doubling (tetraploidization) event in their evo lutionary history, and this is reflected today in patterns of duplicated segments scattered...
Chunfang Zheng, Er Lenert, David Sankoff
Vol. 21 Suppl. 1 2005, pages i502–i508 doi:10.1093/bioinformatics/bti1037
Chromosomal breakpoint reuse in genome sequence rearrangement (2005)
In order to apply gene-order rearrangement algorithms to the comparison of genome sequences, Pevzner and Tesler bypass gene finding and ortholog identification and use the order of homologous blocks...
Genome rearrangements with partially ordered chromosomes,” COCOON (2005)
Abstract Genomic maps often do not specify the order within some groups of two or more markers. The synthesis of a master map from several sources introduces additional order ambiguity due to markers...
Reversal distance for partially ordered genomes (2005)
Zheng, Chunfang, Lenert, Aleksander, Sankoff, David
Motivation: The total order of the genes or markers on a chromosome inherent in its representation as a signed per-mutation must often be weakened to a partial order in the case of real data. This is...
Phil Trinh, Aoife Mclysaght, David Sankoff
Vol. 20 Suppl. 1 2004, pages i318–i325
Chromosomal breakpoint re-use in the inference of genome sequence rearrangement (2004)
In order to apply gene-order rearrangement algorithms to the comparison of genome sequences, Pevzner and Tesler [9] bypass gene finding and ortholog identification, and use the order of homologous...
D.: The statistical significance of max-gap clusters (2004)
Rose Hoberman, David Sankoff, Dannie Dur
Abstract. Identifying gene clusters, genomic regions that share local similarities in gene organization, is a prerequisite for many different types of genomic analyses, including operon prediction,...
D.: The statistical significance of max-gap clusters (2004)
Rose Hoberman, David Sankoff, Dannie Dur
Abstract. Identifying gene clusters, genomic regions that share local similarities in gene organization, is a prerequisite for many different types of genomic analyses, including operon prediction,...
Genomic features in the breakpoint regions between syntenic blocks (2004)
Trinh, Phil, McLysaght, Aoife, Sankoff, David
Motivation: We study the largely unaligned regions between the syntenic blocks conserved in humans and mice, based on data extracted from the UCSC genome browser. These regions contain evolutionary...
Tests for gene clustering (2003)
Comparing chromosomal gene order in two or more related species is an important approach to studying the forces that guide genome organization and evolution. Linked clusters of similar genes found in...
Tests for gene clustering (2003)
Comparing chromosomal gene order in two or more related species is an important approach to studying the forces that guide genome organization and evolution. Linked clusters of similar genes found in...
Short inversions and conserved gene cluster (2002)
Motivation: Two independent sets of recent observations on newly sequenced microbial genomes pertain to the prevalence of short inversion as a gene order rearrangement process and to the lack of...
Early eukaryote evolution based on mitochondrial gene order breakpoints (2000)
David Sankoff, David Bryant, Mélanie Deneault, B. Franz, Lang Gertraud Burger
The comparison of the gene orders in a set of genomes can be used to infer their phylogenetic relationships and to reconstruct ancestral gene orders. For three genomes this is done by solving the...
Early eukaryote evolution based on mitochondrial gene order breakpoints (2000)
David Sankoff, David Bryant, Mélanie Deneault, B. Franz, Lang Gertraud Burger
The comparison of the gene orders in a set of genomes can be used to infer their phylogenetic relationships and to reconstruct ancestral gene orders. For three genomes this is done by solving the...
David Sankoff, Mélanie Deneault, David Bryant, Claude Lemieux, Monique Turmel
Normalizing the number of breakpoints between two genomes, previously reduced by deleting the genes specific to one or the other, gives a rapidly calculated in-dex of gene order evolution which is...
Early eukaryote evolution based on mitochondrial gene order breakpoints (2000)
David Sankoff, David Bryant, Mdlanie Deneault, B. Franz, Lang Gertraud Burger
We present a general heuristic for the median problem for induced breakpoints on genomes with unequal gene con-tent and incorporate this into a routine for estimating op-timal gene orders for the...
Comparative mapping and genome rearrangement (1999)
Comparative mapping of two species allows the observation of chromosomal segments conserved in both genomes since divergence from a common ancestor. Statistical analysis of the distribution of genes...
Phylogenetic invariants for genome rearrangements (1999)
David Sankoff, Mathieu Blanchette
We review the combinatorial optimization problems in calculating edit distances between genomes and phylogenetic inference based on minimizing gene order changes. With a view to avoiding the...
Genome rearrangement with gene families (1999)
Motivation: The theory and practice of genome rearrangement analysis breaks down in the biologically widespread contexts where each gene may be present in a number of copies, not necessarily...
Genome structure and gene content in protist mitochondrial DNAs (1998)
Michael W. Gray, B. Franz Lang, Robert Cedergren, G. Brian Golding, Claude Lemieux, David Sankoff, ...
Although the collection of completely sequenced mitochondrial genomes is expanding rapidly, only recently has a phylogenetically broad representation of mtDNA sequences from protists (mostly...
Phylogenetic invariants for metazoan mitochondrial genome evolution, 22–31 (1998)
David Sankoff, Mathieu Blanchette, Qu'ebec Hc J
The method of phylogenetic invariants was developed to apply to aligned sequence data generated, according to a stochastic substitution model, for N species related through an unknown phylogenetic...
Takashi Kunisawa, David Sankoff
Gene order breakpoint evidence in animal mitochondrial phylogeny
We review the combinatorial optimization problems in calculating edit distances between genomes and phylogenetic inference based on minimizing gene order changes. With a view to avoiding the...
Generating 3D Virtual Populations from Pictures of a Few Individuals (1997)
WonSook Lee, Pierre Beylot, David Sankoff, Nadia Magnenat-Thalmann
. This paper describes a method for cloning faces from two orthogonal pictures and for generating populations from a small number of these clones. An efficient method for reconstructing 3D heads...
The Median Problem for Breakpoints in Comparative Genomics (1997)
David Sankoff, Mathieu Blanchette
During evolution, chromosomal rearrangements, such as reciprocal translocation, transposition and inversion, disrupt gene content and gene order on chromosomes. We discuss algorithmic and statistical...
Mathieu Blanchette, Guillaume Bourque, David Sankoff
We describe a number of heuristics for inferring the gene orders of the hypothetical ancestral genomes in a fixed phylogeny. The optimization criterion is the minimum number of breakpoints (pairs of...
Steiner Points in the Space of Genome Rearrangements (1996)
David Sankoff, Gopalakrishnan Sundaram, John Kececioglu
We present some experiences with the problem of multiple genome comparison, analogous to multiple sequence alignment in sequence comparison, under the inversion and transposition distance metrics,...
John Kececioglu, David Sankoff
Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest...
Gray, Michael W., Sankoff, David, Cedergren, Robert J.
To probe the earliest evolutionary events attending the origin of the five known genome types (archaebacterial, eubacterial, nuclear, mitochondrial and plastid), we have analyzed sequences...
A strategy for sequence phylogeny research (1982)
Sankoff, David, Cedergren, R.J., McKay, W.
Minimal mutation trees, and almost minimal trees, are constructed from two data sets, one of phenylalanine tRNA sequences, and the other of 5S RNA sequences, from a diverse range of organisms. The...
Singularities in the analysis of binomial data (1978)
ROUSSEAU, PASCALE, SANKOFF, DAVID
Transformed additive models accounting for the factors influencing a binomial probability sometimes give rise to infinite maximum likelihood estimates. Necessary and sufficient conditions for a...
Duration of detectible synchrony in a binary branching process (1971)
An index for synchrony is defined, based on the age distribution of a population, which can be evaluated at any time, not only once per cell cycle, and which measures the characteristic of the...
Historical linguistics as stochastic process [microform] / (1969)
Thesis--McGill University.
On the evolutionary origin of the plant mitochondrion and its genome
Gray, Michael W., Cedergren, Robert, Abel, Yvon, Sankoff, David
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...
Matching Sequences under Deletion/Insertion Constraints
Given two finite sequences, we wish to find the longest common subsequences satisfying certain deletion/insertion constraints. Consider two successive terms in the desired subsequence. The distance...
On the evolutionary origin of the plant mitochondrion and its genome
Gray, Michael W., Cedergren, Robert, Abel, Yvon, Sankoff, David
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...
Matching Sequences under Deletion/Insertion Constraints
Given two finite sequences, we wish to find the longest common subsequences satisfying certain deletion/insertion constraints. Consider two successive terms in the desired subsequence. The distance...
David Sankoff, Yvon Abel, Jotun Hein
Local optimization, Heuristics, Molecular evolution,
An efficient algorithm for supertrees
Mariana Constantinescu, David Sankoff
Tree compatibility, Constraints on trees, Supertrees, Consensus trees,
Tree enumeration modulo a consensus
Mariana Constantinescu, David Sankoff
Consensus, Tree enumeration,
The inference of hierarchical schemes for multinomial data
Pascale Rousseau, David Sankoff
Hierarchical classification, Multinomial, Likelihood, Logistic regression,
We study the small phylogeny problem in the space of multichromosomal genomes under the double cut and join metric. This is similar to the existing MGR (multiple genome rearrangements) approach but...
Genome Halving with an Outgroup
Zheng, Chunfang, Zhu, Qian, Sankoff, David
Some genomes are known to have incurred a genome doubling (tetraploidization) event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout...
Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes
Zheng, Chunfang, Zhu, Qian, Adam, Zaky, Sankoff, David
Motivation: Some present day species have incurred a whole genome doubling event in their evolutionary history, and this is reflected today in patterns of duplicated segments scattered throughout...
The where and wherefore of evolutionary breakpoints
The 'action' in genome-level evolution lies not in the large gene-containing segments that are conserved among related species, but in the breakpoint regions between these segments. Two recent papers...