Theoretical and practical advances in genome halving

MOTIVATION: Duplication of an organism's entire genome is a rare but spectacular event, enabling the rapid emergence of multiple new gene functions. Over time, the parallel linkage of duplicated genes across chromosomes may be disrupted by reciprocal translocations, while the intra-chromosomal order of genes may be shuffled by inversions and transpositions. Some duplicate genes may evolve unrecognizably or be deleted. As a consequence, the only detectable signature of an ancient duplication event in a modern genome may be the presence of various chromosomal segments containing parallel paralogous genes, with each segment appearing exactly twice in the genome. The problem of reconstructing the linkage structure of an ancestral genome before duplication is known as genome halving with unordered chromosomes. RESULTS: In this paper, we derive a new upper bound on the genome halving distance that is tighter than the best known, and a new lower bound that is almost always tighter than the best known. We also define the notion of genome halving diameter, and obtain both upper and lower bounds for it. Our tighter bounds on genome halving distance yield a new algorithm for reconstructing an ancestral duplicated genome. We create a software package GenomeHalving based on this new algorithm and test it on the yeast genome, identifying a sequence of translocations for halving the yeast genome that is shorter than previously conjectured possible.     

Dynamics of genome rearrangement in bacterial populations

Genome structure variation has profound impacts on phenotype in organisms ranging from microbes to humans, yet little is known about how natural selection acts on genome arrangement. Pathogenic bacteria such as Yersinia pestis, which causes bubonic and pneumonic plague, often exhibit a high degree of genomic rearrangement. The recent availability of several Yersinia genomes offers an unprecedented opportunity to study the evolution of genome structure and arrangement. We introduce a set of statistical methods to study patterns of rearrangement in circular chromosomes and apply them to the Yersinia. We constructed a multiple alignment of eight Yersinia genomes using Mauve software to identify 78 conserved segments that are internally free from genome rearrangement. Based on the alignment, we applied Bayesian statistical methods to infer the phylogenetic inversion history of Yersinia. The sampling of genome arrangement reconstructions contains seven parsimonious tree topologies, each having different histories of 79 inversions. Topologies with a greater number of inversions also exist, but were sampled less frequently. The inversion phylogenies agree with results suggested by SNP patterns. We then analyzed reconstructed inversion histories to identify patterns of rearrangement. We confirm an over-representation of "symmetric inversions"-inversions with endpoints that are equally distant from the origin of chromosomal replication. Ancestral genome arrangements demonstrate moderate preference for replichore balance in Yersinia. We found that all inversions are shorter than expected under a neutral model, whereas inversions acting within a single replichore are much shorter than expected. We also found evidence for a canonical configuration of the origin and terminus of replication. Finally, breakpoint reuse analysis reveals that inversions with endpoints proximal to the origin of DNA replication are nearly three times more frequent. Our findings represent the first characterization of genome arrangement evolution in a bacterial population evolving outside laboratory conditions. Insight into the process of genomic rearrangement may further the understanding of pathogen population dynamics and selection on the architecture of circular bacterial chromosomes.     

Structural and functional comparative mapping between the Brassica A genomes in allotetraploid Brassica napus and diploid Brassica rapa

Brassica napus (AACC genome) is an important oilseed crop that was formed by the fusion of the diploids B. rapa (AA) and B. oleracea (CC). The complete genomic sequence of the Brassica A genome will be available soon from the B. rapa genome sequencing project, but it is not clear how informative the A genome sequence in B. rapa (A(r)) will be for predicting the structure and function of the A subgenome in the allotetraploid Brassica species B. napus (A(n)). In this paper, we report the results of structural and functional comparative mapping between the A subgenomes of B. napus and B. rapa based on genetic maps that were anchored with bacterial artificial chromosomes (BACs)-sequence of B. rapa. We identified segmental conservation that represented by syntenic blocks in over one third of the A genome; meanwhile, comparative mapping of quantitative trait loci for seed quality traits identified a dozen homologous regions with conserved function in the A genome of the two species. However, several genomic rearrangement events, such as inversions, intra- and inter-chromosomal translocations, were also observed, covering totally at least 5% of the A genome, between allotetraploid B. napus and diploid B. rapa. Based on these results, the A genomes of B. rapa and B. napus are mostly functionally conserved, but caution will be necessary in applying the full sequence data from B. rapa to the B. napus as a result of genomic rearrangements in the A genome between the two species.     

Structural alterations from multiple displacement amplification of a human genome revealed by mate-pair sequencing

Comprehensive identification of the acquired mutations that cause common cancers will require genomic analyses of large sets of tumor samples. Typically, the tissue material available from tumor specimens is limited, which creates a demand for accurate template amplification. We therefore evaluated whether phi29-mediated whole genome amplification introduces false positive structural mutations by massive mate-pair sequencing of a normal human genome before and after such amplification. Multiple displacement amplification led to a decrease in clone coverage and an increase by two orders of magnitude in the prevalence of inversions, but did not increase the prevalence of translocations. While multiple strand displacement amplification may find uses in translocation analyses, it is likely that alternative amplification strategies need to be developed to meet the demands of cancer genomics.     

Chromosomal translocations and palindromic AT-rich repeats

Repetitive DNA sequences constitute 30% of the human genome, and are often sites of genomic rearrangement. Recently, it has been found that several constitutional translocations, especially those that involve chromosome 22, take place utilizing palindromic sequences on 22q11 and on the partner chromosome. Analysis of translocation junction fragments shows that the breakpoints of such palindrome-mediated translocations are localized at the center of palindromic AT-rich repeats (PATRRs). The presence of PATRRs at the breakpoints indicates a palindrome-mediated mechanism involved in the generation of these constitutional translocations. Identification of these PATRR-mediated translocations suggests a universal pathway for gross chromosomal rearrangement in the human genome. De novo occurrences of PATRR-mediated translocations can be detected by PCR in normal sperm samples but not somatic cells. Polymorphisms of various PATRRs influence their propensity for adopting a secondary structure, which in turn affects de novo translocation frequency. We propose that the PATRRs form an unstable secondary structure, which leads to double-strand breaks at the center of the PATRR. The double-strand breaks appear to be followed by a non-homologous end-joining repair pathway, ultimately leading to the translocations. This review considers recent findings concerning the mechanism of meiosis-specific, PATRR-mediated translocations.     

Group-theoretic models of the inversion process in bacterial genomes

The variation in genome arrangements among bacterial taxa is largely due to the process of inversion. Recent studies indicate that not all inversions are equally probable, suggesting, for instance, that shorter inversions are more frequent than longer, and those that move the terminus of replication are less probable than those that do not. Current methods for establishing the inversion distance between two bacterial genomes are unable to incorporate such information. In this paper we suggest a group-theoretic framework that in principle can take these constraints into account. In particular, we show that by lifting the problem from circular permutations to the affine symmetric group, the inversion distance can be found in polynomial time for a model in which inversions are restricted to acting on two regions. This requires the proof of new results in group theory, and suggests a vein of new combinatorial problems concerning permutation groups on which group theorists will be needed to collaborate with biologists. We apply the new method to inferring distances and phylogenies for published Yersinia pestis data.     

The genome of Salmonella enterica serovar gallinarum: distinct insertions/deletions and rare rearrangements

Salmonella enterica serovar Gallinarum is a fowl-adapted pathogen, causing typhoid fever in chickens. It has the same antigenic formula (1,9,12:--:--) as S. enterica serovar Pullorum, which is also adapted to fowl but causes pullorum disease (diarrhea). The close relatedness but distinct pathogeneses make this pair of fowl pathogens good models for studies of bacterial genomic evolution and the way these organisms acquired pathogenicity. To locate and characterize the genomic differences between serovar Gallinarum and other salmonellae, we constructed a physical map of serovar Gallinarum strain SARB21 by using I-CeuI, XbaI, and AvrII with pulsed-field gel electrophoresis techniques. In the 4,740-kb genome, we located two insertions and six deletions relative to the genome of S. enterica serovar Typhimurium LT2, which we used as a reference Salmonella genome. Four of the genomic regions with reduced lengths corresponded to the four prophages in the genome of serovar Typhimurium LT2, and the others contained several smaller deletions relative to serovar Typhimurium LT2, including regions containing srfJ, std, and stj and gene clusters encoding a type I restriction system in serovar Typhimurium LT2. The map also revealed some rare rearrangements, including two inversions and several translocations. Further characterization of these insertions, deletions, and rearrangements will provide new insights into the molecular basis for the specific host-pathogen interactions and mechanisms of genomic evolution to create a new pathogen.     

Genome mapping in capsicum and the evolution of genome structure in the solanaceae.

We have created a genetic map of Capsicum (pepper) from an interspecific F2 population consisting of 11 large (76.2-192.3 cM) and 2 small (19.1 and 12.5 cM) linkage groups that cover a total of 1245.7 cM. Many of the markers are tomato probes that were chosen to cover the tomato genome, allowing comparison of this pepper map to the genetic map of tomato. Hybridization of all tomato-derived probes included in this study to positions throughout the pepper map suggests that no major losses have occurred during the divergence of these genomes. Comparison of the pepper and tomato genetic maps showed that 18 homeologous linkage blocks cover 98.1% of the tomato genome and 95.0% of the pepper genome. Through these maps and the potato map, we determined the number and types of rearrangements that differentiate these species and reconstructed a hypothetical progenitor genome. We conclude there have been 30 breaks as part of 5 translocations, 10 paracentric inversions, 2 pericentric inversions, and 4 disassociations or associations of genomic regions that differentiate tomato, potato, and pepper, as well as an additional reciprocal translocation, nonreciprocal translocation, and a duplication or deletion that differentiate the two pepper mapping parents.     

Characterising chromosome rearrangements: recent technical advances in molecular cytogenetics

Genomic rearrangements can result in losses, amplifications, translocations and inversions of DNA fragments thereby modifying genome architecture, and potentially having clinical consequences. Many genomic disorders caused by structural variation have initially been uncovered by early cytogenetic methods. The last decade has seen significant progression in molecular cytogenetic techniques, allowing rapid and precise detection of structural rearrangements on a whole-genome scale. The high resolution attainable with these recently developed techniques has also uncovered the role of structural variants in normal genetic variation alongside single-nucleotide polymorphisms (SNPs). We describe how array-based comparative genomic hybridisation, SNP arrays, array painting and next-generation sequencing analytical methods (read depth, read pair and split read) allow the extensive characterisation of chromosome rearrangements in human genomes.     

A detailed synteny map of the eggplant genome based on conserved ortholog set II (COSII) markers

We report herein the mapping of 115 PCR-based orthologous markers, including 110 conserved ortholog set or COSII markers, on the reference RFLP map of eggplant. The result permitted inference of a detailed syntenic relationship between the eggplant and tomato genomes. Further, the position of additional 522 COSII markers was inferred in the eggplant map via eggplant-tomato synteny, bringing the total number of markers in the eggplant genome to 869. Since divergence from their last common ancestor approximately 12 million years ago, the eggplant and tomato genomes have become differentiated by a minimum number of 24 inversions and 5 chromosomal translocations, as well as a number of single gene transpositions possibly triggered by transposable elements. Nevertheless, the two genomes share 37 conserved syntenic segments (CSSs) within which gene/marker order is well preserved. The high-resolution COSII synteny map described herein provides a platform for cross-reference of genetic and genomic information (including the tomato genome sequence) between eggplant and tomato and therefore will facilitate both applied and basic research in eggplant. Electronic supplementary material  The online version of this article (doi:) contains supplementary material, which is available to authorized users.     

Comparative BAC‐based physical mapping of Oryza sativa ssp. indica var. 93–11 and evaluation of the two rice reference sequence assemblies

Reference sequences are sequences that are used for public consultation, and therefore must be of high quality. Using the whole‐genome shotgun/next‐generation sequencing approach, many genome sequences of complex higher plants have been generated in recent years, and are generally considered reference sequences. However, none of these sequences has been experimentally evaluated at the whole‐genome sequence assembly level. Rice has a relatively simple plant genome, and the genome sequences for its two sub‐species obtained using different sequencing approaches were published approximately 10 years ago. This provides a unique system for a case study to evaluate the qualities and utilities of published plant genome sequences. We constructed a robust BAC physical map embedding a large number of BAC end sequences forrice variety 93–11. Through BAC end sequence alignments and tri‐assembly comparisons of the 93–11 physical map and the two reference sequences, we found that the Nipponbare reference sequence generated using the clone‐by‐clone approach has a high quality but still contains small artifact inversions and missing sequences. In contrast, the 93–11 reference sequence generated using the whole‐genome shotgun approach contains many large and varied assembly errors, such as inversions, duplications and translocations, as well as missing sequences. The 93–11 physical map provides an invaluable resource for evaluation and improvements toward completion of both Nipponbare and 93–11 reference sequences.     

Restricted DCJ model: rearrangement problems with chromosome reincorporation

We study three classical problems of genome rearrangement--sorting, halving, and the median problem--in a restricted double cut and join (DCJ) model. In the DCJ model, introduced by Yancopoulos et al., we can represent rearrangement events that happen in multichromosomal genomes, such as inversions, translocations, fusions, and fissions. Two DCJ operations can mimic transpositions or block interchanges by first extracting an appropriate segment of a chromosome, creating a temporary circular chromosome, and then reinserting it in its proper place. In the restricted model, we are concerned with multichromosomal linear genomes and we require that each circular excision is immediately followed by its reincorporation. Existing linear-time DCJ sorting and halving algorithms ignore this reincorporation constraint. In this article, we propose a new algorithm for the restricted sorting problem running in O(n log n) time, thus improving on the known quadratic time algorithm. We solve the restricted halving problem and give an algorithm that computes a multilinear halved genome in linear time. Finally, we show that the restricted median problem is NP-hard as conjectured.     

Comparative chromosome painting defines the high rate of karyotype changes between pigs and bovids

Human and sheep chromosome-specific probes were used to construct comparative painting maps between the pig (Suiformes), cattle and sheep (Bovidae), and humans. Various yet unknown translocations were observed that would assist in a more complete reconstruction of homology maps of these species. The number of homologous segments that can be identified with sheep probes in the pig karyotype exceeds that described previously by chromosome painting between two non-primate mammals belonging to the same order. Sheep probes painted 62 segments on pig autosomes and delineated not only translocations, but also 9 inversions. All inversions were paracentric and indicate that these rearrangements may be characteristic for chromosomal changes in suiforms. Hybridizations of all sheep painting probes to cattle chromosomes confirmed the chromosome conservation in bovids. In addition, we observed a small translocation that was previously postulated from linkage mapping data, but was not yet described by physical mapping. The chromosome painting data are complemented with a map of available comparative gene mapping data between pig and sheep genomes. A detailed table listing the comparative gene mapping data between pig and cattle genomes is provided. The reanalysis of the pig karyotype with a new generation of human paint probes provides an update of the human/pig comparative genome map and demonstrates two new chromosome homologies. Seven conserved segments not yet identified by chromosome painting are also reported. Received: 2 October 2000 / Accepted: 15 January 2001     

LD-CNV: rapid and simple discovery of chromosomal translocations using linkage disequilibrium between copy number variable loci

Large-scale structural variations, such as chromosomal translocations, can have profound effects on fitness and phenotype, but are difficult to identify and characterize. Here, we describe a simple and effective method aimed at identifying translocations using only the dosage of sequence reads mapped on the reference genome. We binned reads on genomic segments sized according to sequencing coverage and identified instances when copy number segregated in populations. For each dosage-polymorphic 1 Mb bin, we tested independence, effectively an apparent linkage disequilibrium (LD), with other variable bins. In nine potato (Solanum tuberosum) dihaploid families translocations affecting pericentromeric regions were common and in two cases were due to genomic misassembly. In two populations, we found evidence for translocation affecting euchromatic arms. In cv. PI 310467, a nonreciprocal translocation between chromosomes (chr.) 7 and 8 resulted in a 5–3 copy number change affecting several Mb at the respective chromosome tips. In cv. “Alca Tarma,” the terminal arm of chr. 4 translocated to the tip of chr. 1. Using oligonucleotide-based fluorescent in situ hybridization painting probes (oligo-FISH), we tested and confirmed the predicted arrangement in PI 310467. In 192 natural accessions of Arabidopsis thaliana, dosage haplotypes tended to vary continuously and resulted in higher noise, while apparent LD between pericentromeric regions suggested the effect of repeats. This method, LD-CNV, should be useful in species where translocations are suspected because it tests linkage without the need for genotyping.     

Measuring genome divergence in bacteria: a case study using chlamydian data

We have studied the relative contribution of inversions, transpositions, deletions, and nucleotide substitutions to the evolution of Chlamydia trachomatis and Chlamydia pneumoniae. The minimal number of rearrangement events required for converting the gene order structure of one genome into that of the other was estimated to 59 +/- 6 events, including 13% inversions, 38% short inversions, and 49% transpositions. In contrast to previous findings, no examples of horizontal gene transfer subsequent to species divergence were identified, nor any evidence for an excessive number of tandem gene duplications. A statistical model was used to compare nucleotide frequencies for a set of genes uniquely present in one species to a set of orthologous genes present in both species. The two data sets were not significantly different, which is indicative of a low frequency of horizontal gene transfer events. This is based on the assumption that a foreign gene of different nucleotide content will not have become completely ameliorated, as verified by simulations of the amelioration rate at twofold and fourfold degenerate codon sites. The frequencies of nucleotide substitutions at twofold and fourfold degenerate sites, deletions, inversions, and translocations were estimated to 1.42, 0.62, 0.18, 0.01, and 0.01 per site, respectively.     

Chromosome arm‐specific patterns of polymorphism associated with chromosomal inversions in the major African malaria vector,Anopheles funestus

Chromosomal inversions facilitate local adaptation of beneficial mutations and modulate genetic polymorphism, but the extent of their effects within the genome is still insufficiently understood. The genome of Anopheles funestus, a malaria mosquito endemic to sub‐Saharan Africa, contains an impressive number of paracentric polymorphic inversions, which are unevenly distributed among chromosomes and provide an excellent framework for investigating the genomic impacts of chromosomal rearrangements. Here, we present results of a fine‐scale analysis of genetic variation within the genome of two weakly differentiated populations of Anopheles funestus inhabiting contrasting moisture conditions in Cameroon. Using population genomic analyses, we found that genetic divergence between the two populations is centred on regions of the genome corresponding to three inversions, which are characterized by high values of F_ST, absolute sequence divergence and fixed differences. Importantly, in contrast to the 2L chromosome arm, which is collinear, nucleotide diversity is significantly reduced along the entire length of three autosome arms bearing multiple overlapping chromosomal rearrangements. These findings support the idea that interactions between reduced recombination and natural selection within inversions contribute to sculpt nucleotide polymorphism across chromosomes in An. funestus.