Reversals of Fortune
Lecture notes in computer sciencePublished 1 January 2005
David Sankoff, Chungfang Zheng, Aleksander Lenert
Citations21
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work combines heuristics for the first two problems with an exact algorithm for the third to solve a moderate-sized instance comparing maps of cereal genomes.
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 hard: 1) Orientation assignment for unsigned genomes. 2 ) Ortholog identification in the presence of multiple copies of genes. 3) Linearisation of partially ordered genomes. The comparison of traditional genetic maps by rearrangement algorithms poses all these problems. We combine heuristics for the first two problems with an exact algorithm for the third to solve a moderate-sized instance comparing maps of cereal genomes.
Keywords
Agricultural and Biological SciencesBiochemistry, Genetics and Molecular Biology
Proceedings of the National Academy of SciencesDNA sequence evidence for the segmental allotetraploid origin of maize
698 Citations1997Brandon S. Gaut, John Doebley
The analyses indicate that coalescent times for duplicated sequences fall into two distinct groups, corresponding to roughly 20.5 and 11.4 million years, which strongly discounts the possibility that the maize genome is the product of a genomic allotetraploid event, and also suggests that one of the two ancestral diploids shares a more recent common ancestor with sorghum than it does with the other ancestraldiploid.
Computer applications in the biosciencesEfficient sorting of genomic permutations by translocation, inversion and block interchange
503 Citations2005Sophia Yancopoulos, Oliver Attie +1 more
Proceedings of the National Academy of SciencesGene order comparisons for phylogenetic inference: evolution of the mitochondrial genome.
429 Citations1992David Sankoff, Guillaume Leduc +4 more
This work describes the construction of a database of 16 mitochondrial gene orders from fungi and other eukaryotes by using complete or nearly complete genomic sequences, and proposes 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.
NatureThe Mechanism of Mendelian Heredity
355 Citations1916T. H. Morgan, Bridges, Calvin Blackman, 1889- joint author. +2 more
The Mechanism of Mendelian Heredity sets forth clearly and within reasonable compass the latest deductions and speculations of genetic research.
Proceedings of the National Academy of SciencesHuman and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution
354 Citations2003Pavel A. Pevzner, Glenn Tesler
The genome rearrangement analysis of the human and mouse genomes implies the existence of a large number of very short “hidden” synteny blocks that were invisible in the comparative mapping data and ignored in the random breakage model, suggesting a model of chromosome evolution that postulates that mammalian genomes are mosaics of fragile regions with high propensity for rearrangements and solid regions with low propensity for reorganisation.
Transforming men into mice (polynomial algorithm for genomic distance problem)
330 Citations2002Sridhar Hannenhalli, Pavel A. Pevzner
A duality theorem is proved which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings and leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios for human-mouse evolution.
BioinformaticsGRIMM: genome rearrangements web server
328 Citations2002Glenn Tesler
Genome Rearrangements In Man and Mouse (GRIMM) is a tool for analyzing rearrangements of gene orders in pairs of unichROMosomal and multichromosomal genomes, with either signed or unsigned gene data.
Transforming cabbage into turnip
268 Citations1995Sridhar Hannenhalli, Pavel A. Pevzner
Sorting of signed permutations by reversals is studied, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA and proves a duality theorem explaining this intriguing performance.
Genome ResearchReconstructing the Genomic Architecture of Ancestral Mammals: Lessons From Human, Mouse, and Rat Genomes
241 Citations2004Guillaume Bourque, Pavel A. Pevzner +1 more
Three-way analysis of rearrangements leads to a reliable reconstruction of the genomic architecture of specific regions in the murid ancestor, including the X chromosome, and for the first time allows one to assign major rearrangement events to one of human, mouse, and rat lineages.
Nucleic Acids ResearchGramene: a resource for comparative grass genomics
231 Citations2002Doreen Ware
Gramene replaces the existing AceDB database 'RiceGenes' with a relational database based on Oracle, which aims to use the rice genetic, physical and sequence maps as fundamental organizing units, to provide a common denominator for moving from one crop grass to another and to serve as a portal for interconnecting with other web-based crop grass resources.
Plant Molecular BiologyA high-density genetic map of Sorghum bicolor (L.) Moench based on 2926 AFLP®, RFLP and SSR markers
231 Citations2002Monica A. Menz, Robert R. Klein +4 more
How the information contained in this map is being integrated into a sorghum physical map for map-based gene isolation, comparative genome analysis, and as a source of sequence-ready clones for genome sequencing projects is discussed.
BioinformaticsGenome rearrangement with gene families
222 Citations1999David Sankoff
Simulations show that in two random genomes, the expected exemplar distance/n is sensitive to the number and size of gene families, but approaches 1 as the number of singleton families increases, while basing exemplardistance on exemplar reversals distance (ERD), the expected computing cost depends on the configuration of genes but is not sensitive to n.
GeneticsA High-Density Genetic Recombination Map of Sequence-Tagged Sites for <i>Sorghum</i>, as a Framework for Comparative Structural and Evolutionary Genomics of Tropical Grains and Grasses
210 Citations2003John Bowers, Colette A. Abbey +22 more
A genetic recombination map for Sorghum of 2512 loci spaced at average 0.4 cM intervals based on 2050 RFLP probes is reported, supporting and extending prior findings regarding maize-sorghum synteny-in particular, where 45% of comparative loci fall outside the inferred colinear/syntenic regions, suggesting that many small rearrangements have occurred since maize-edinburgh divergence.
Journal of Computer and System SciencesEfficient algorithms for multichromosomal genome rearrangements
165 Citations2002Glenn Tesler
Improved the speed by combining the algorithm with the algorithm of Bader et al. that computes reversal distances for permutations in linear time and improved the construction by fixing some problems with the construction.
Genome ResearchComparative architectures of mammalian and chicken genomes reveal highly variable rates of genomic rearrangements across different lineages
161 Citations2004Guillaume Bourque, Evgeny M. Zdobnov +3 more
This analysis reveals a very low rate of rearrangements in chicken, in the early mammalian ancestor, or in both, and suggests the suggested number of interchromosomal rearrangement between the mammalian ancestor and chicken only slightly exceeds the number that happened in the mouse lineage over the course of about 87 million years.
IEEE/ACM Transactions on Computational Biology and BioinformaticsAssignment of Orthologous Genes via Genome Rearrangement
160 Citations2005Xin Chen, Jie Zheng +5 more
A new approach to ortholog assignment that takes into account both sequence similarity and evolutionary events at a genome level, where orthologous genes are assumed to correspond to each other in the most parsimonious evolving scenario under genome rearrangement is presented.
Information Processing LettersSorting permutations by block-interchanges
160 Citations1996David A. Christie
A polynomial-time algorithm is demonstrated for calculating the block-interchange distance of a permutation (i.e. the minimum number of block- interchanges required to transform the permutation to the identity).
Current GeneticsEvolutionary significance of inversions in legume chloroplast DNAs
136 Citations1988Jeffrey D. Palmer, Bernardita Osorio +1 more
Analysis of gene locations in pea cpDNA, which lacks the large inverted repeat, combined with cross-hybridization studies using 59 clones covering the mung bean genome, leads to a refined picture of the position and nature of the numerous rearrangements previously described in the pea genome.
SIAM Journal on ComputingThe Reconstruction of Doubled Genomes
98 Citations2003Nadia El-Mabrouk, David Sankoff
This work presents exact algorithms for reconstructing the ancestral doubled genome in linear time, minimizing the number of rearrangement mutations required to derive the observed order of genes along the present-day chromosomes.
Computational biologyThe Complexity of Calculating Exemplar Distances
94 Citations2000David Bryant
Here it is shown that the calculation of the exemplar distance between two genomes is NP-hard for both the signed reversals distance and the breakpoint distance.
Lecture notes in computer scienceExact and approximation algorithms for the inversion distance between two chromosomes
81 Citations2005John Kececioglu, David Sankoff
This work considers the problem of computing the shortest series of reversals that transform one permutation to another, and takes an arbitrary substring of elements and reverses their order.
Symposium on Discrete AlgorithmsTo cut…or not to cut (applications of comparative physical maps in molecular evolution)
53 Citations1996Sridhar Hannenhalli, Pavel A. Pevzner
SIAM Journal on Discrete MathematicsReversals and Transpositions Over Finite Alphabets
52 Citations2005A. J. Radcliffe, Alex Scott +1 more
It is shown that determining reversal, transposition, or signed reversal distance between two strings over a finite alphabet is NP-hard, while for "dense" instances the authors give a polynomial-time approximation scheme.
Computer applications in the biosciencesDivide-and-conquer approach for the exemplar breakpoint distance
41 Citations2005Cuong Nguyen, Ywee Chieh Tay +1 more
This paper proposes a divide-and-conquer approach for calculating the exemplar breakpoint distance between two genomes with multiple gene families and shows that this program is much more efficient than the existing program that is based only on the branch- and-bound technique.
Lecture notes in computer sciencePhylogenetic Reconstruction from Gene-Rearrangement Data with Unequal Gene Content
36 Citations2003Jijun Tang, Bernard M. E. Moret
Extensions to the GRAPPA approach are presented that can handle limited numbers of duplications (one of the main requirements for analyzing genomic data from organelles) and a few deletions and show that, in practice, the bounding functions suffice to prune away almost all of the search space.
Lecture notes in computer scienceConserved Interval Distance Computation Between Non-trivial Genomes
35 Citations2005Guillaume Blin, Roméo Rizzi
The time complexity of the conserved interval distance computation considering duplicated genes using both the examplar distance and the gene matching computation using both those two strategies are studied.
Computational biologyComparative Genomics
32 Citations2000
The generation of monoclonal antibody specific to P. aeruginosa without cross reaction to other bacterial species is reported without cross reaction to other bacterial species.
Lecture notes in computer scienceMaximizing Synteny Blocks to Identify Ancestral Homologs
30 Citations2005Guillaume Bourque, Yasmine Yacef +1 more
Different measures of order conservation are compared to select, among a gene family, the pair of copies in two genomes that best reflects the common ancestor, by maximizing synteny blocks between genomes.
Computer applications in the biosciencesReversal distance for partially ordered genomes
27 Citations2005Chunfang Zheng, Aleksander Lenert +1 more
This work formalizes the uncertainty in gene order data by representing a chromosome from each genome as a partial order, summarized by a directed acyclic graph (DAG), and aims to infer a minimal sequence of reversals for transforming any topological sort of one DAG to any one of the other DAG.
INFORMS journal on computingSorting Permutations by Reversals Through Branch-and-Price
27 Citations2001Alberto Caprara, Giuseppe Lancia +1 more
An exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in molecular biology, based on an integer linear programming formulation of a graph-theoretic relaxation of the problem, calling for a decomposition of the edge set of a bicolored graph into the maximum number of alternating cycles.
Computational biologyDuplication, Rearrangement, and Reconciliation
26 Citations2000David Sankoff, Nadia El-Mabrouk
Gene orders, together with gene trees produced by sequence comparison, are submitted to an analysis that integrates the concepts of phylogenetic reconciliation, exemplar strings and breakpoint medians.
Journal of Combinatorial OptimizationGenome rearrangements with partially ordered chromosomes
8 Citations2006Chunfang Zheng, David Sankoff
This work represents each chromosome as a partial order, summarized by a directed acyclic graph (DAG), to account for poor resolution and missing data, and extracts a maximal decomposition into alternating coloured cycles, determining an optimal sequence of rearrangements.
Lecture notes in computer scienceGenome Rearrangements with Partially Ordered Chromosomes
7 Citations2005Chunfang Zheng, David Sankoff