Dataset Information

The gene family-free median of three.

ABSTRACT: BACKGROUND:The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the breakpoint median of three genomes, which asks for the construction of a fourth genome that minimizes the sum of breakpoint distances to the input genomes. METHODS:We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We study its computational complexity and we describe an integer linear program (ILP) for its exact solution. We further discuss a related problem called family-free adjacencies for k genomes for the special case of [Formula: see text] and present an ILP for its solution. However, for this problem, the computation of exact solutions remains intractable for sufficiently large instances. We then proceed to describe a heuristic method, FFAdj-AM, which performs well in practice. RESULTS:The developed methods compute accurate positional orthologs for genomes comparable in size of bacterial genomes on simulated data and genomic data acquired from the OMA orthology database. In particular, FFAdj-AM performs equally or better when compared to the well-established gene family prediction tool MultiMSOAR. CONCLUSIONS:We study the computational complexity of a new family-free model and present algorithms for its solution. With FFAdj-AM, we propose an appealing alternative to established tools for identifying higher confidence positional orthologs.

SUBMITTER: Doerr D

PROVIDER: S-EPMC5446766 | biostudies-literature | 2017

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

The gene family-free median of three.

Doerr Daniel D Balaban Metin M Feijão Pedro P Chauve Cedric C

Algorithms for molecular biology : AMB 20170526

<h4>Background</h4>The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the breakpoint median of three genomes, which asks for the construction of a fourth genome that minimizes the sum of breakpoint distances to the input genomes.<h4>Methods</h4>We present a model for constructing a median of three genomes in th ...[more]

PMID: 28559921

Similar Datasets

Project description:BackgroundSugarcane is an economically important crop contributing about 80% and 40% to the world sugar and ethanol production, respectively. The complicated genetics consequential to its complex polyploid genome, however, have impeded efforts to improve sugar yield and related important agronomic traits. Modern sugarcane cultivars are complex hybrids derived mainly from crosses among its progenitor species, S. officinarum and S. spontanuem, and to a lesser degree, S. robustom. Atypical of higher plants, sugarcane stores its photoassimilates as sucrose rather than as starch in its parenchymous stalk cells. In the sugar biosynthesis pathway, sucrose synthase (SuSy, UDP-glucose: D-fructose 2-a-D-glucosyltransferase, EC 2.4.1.13) is a key enzyme in the regulation of sucrose accumulation and partitioning by catalyzing the reversible conversion of sucrose and UDP into UDP-glucose and fructose. However, little is known about the sugarcane SuSy gene family members and hence no definitive studies have been reported regarding allelic diversity of SuSy gene families in Saccharum species.ResultsWe identified and characterized a total of five sucrose synthase genes in the three sugarcane progenitor species through gene annotation and PCR haplotype analysis by analyzing 70 to 119 PCR fragments amplified from intron-containing target regions. We detected all but one (i.e. ScSuSy5) of ScSuSy transcripts in five tissue types of three Saccharum species. The average SNP frequency was one SNP per 108 bp, 81 bp, and 72 bp in S. officinarum, S. robustom, and S. spontanuem respectively. The average shared SNP is 15 between S. officinarum and S. robustom, 7 between S. officinarum and S. spontanuem , and 11 between S. robustom and S. spontanuem. We identified 27, 35, and 32 haplotypes from the five ScSuSy genes in S. officinarum, S. robustom, and S. spontanuem respectively. Also, 12, 11, and 9 protein sequences were translated from the haplotypes in S. officinarum, S. robustom, S. spontanuem, respectively. Phylogenetic analysis showed three separate clusters composed of SbSuSy1 and SbSuSy2, SbSuSy3 and SbSuSy5, and SbSuSy4.ConclusionsThe five members of the SuSy gene family evolved before the divergence of the genera in the tribe Andropogoneae at least 12 MYA. Each ScSuSy gene showed at least one non-synonymous substitution in SNP haplotypes. The SNP frequency is the lowest in S. officinarum, intermediate in S. robustum, and the highest in S. spontaneum, which may reflect the timing of the two rounds of whole genome duplication in these octoploids. The higher rate of shared SNP frequency between S. officinarum and S. robustum than between S. officinarum and in S. spontaneum confirmed that the speciation event separating S. officinarum and S. robustum occurred after their common ancestor diverged from S. spontaneum. The SNP and haplotype frequencies in three Saccharum species provide fundamental information for designing strategies to sequence these autopolyploid genomes.

Project description:BackgroundA classical problem in comparative genomics is to compute the rearrangement distance, that is the minimum number of large-scale rearrangements required to transform a given genome into another given genome. The traditional approaches in this area are family-based, i.e., require the classification of DNA fragments of both genomes into families. Furthermore, the most elementary family-based models, which are able to compute distances in polynomial time, restrict the families to occur at most once in each genome. In contrast, the distance computation in models that allow multifamilies (i.e., families with multiple occurrences) is NP-hard. Very recently, Bohnenkämper et al. (J Comput Biol 28:410-431, 2021) proposed an ILP formulation for computing the genomic distance of genomes with multifamilies, allowing structural rearrangements, represented by the generic double cut and join (DCJ) operation, and content-modifying insertions and deletions of DNA segments. This ILP is very efficient, but must maximize a matching of the genes in each multifamily, in order to prevent the free lunch artifact that would otherwise let empty or almost empty matchings give smaller distances.ResultsIn this paper, we adopt the alternative family-free setting that, instead of family classification, simply uses the pairwise similarities between DNA fragments of both genomes to compute their rearrangement distance. We adapted the ILP mentioned above and developed a model in which pairwise similarities are used to assign weights to both matched and unmatched genes, so that an optimal solution does not necessarily maximize the matching. Our model then results in a natural family-free genomic distance, that takes into consideration all given genes, without prior classification into families, and has a search space composed of matchings of any size. In spite of its bigger search space, our ILP seems to be boosted by a reduction of the number of co-optimal solutions due to the weights. Indeed, it converged faster than the original one by Bohnenkämper et al. for instances with the same number of multiple connections. We can handle not only bacterial genomes, but also fungi and insects, or sets of chromosomes of mammals and plants. In a comparison study of six fruit fly genomes, we obtained accurate results.

Project description:BackgroundIn plants, carotenoids serve as the precursors to C13-norisoprenoids, a group of apocarotenoid compounds with diverse biological functions. Enzymatic cleavage of carotenoids catalysed by members of the carotenoid cleavage dioxygenase (CCD) family has been shown to produce a number of industrially important volatile flavour and aroma apocarotenoids including β-ionone, geranylacetone, pseudoionone, α-ionone and 3-hydroxy-β-ionone in a range of plant species. Apocarotenoids contribute to the floral and fruity attributes of many wine cultivars and are thereby, at least partly, responsible for the "varietal character". Despite their importance in grapes and wine; carotenoid cleavage activity has only been described for VvCCD1 and the mechanism(s) and regulation of carotenoid catabolism remains largely unknown.ResultsThree grapevine-derived CCD-encoding genes have been isolated and shown to be functional with unique substrate cleavage capacities. Our results demonstrate that the VvCCD4a and VvCCD4b catalyse the cleavage of both linear and cyclic carotenoid substrates. The expression of VvCCD1, VvCCD4a and VvCCD4b was detected in leaf, flower and throughout berry development. VvCCD1 expression was constitutive, whereas VvCCD4a expression was predominant in leaves and VvCCD4b in berries. A transgenic population with a 12-fold range of VvCCD1 expression exhibited a lack of correlation between VvCCD1 expression and carotenoid substrates and/or apocarotenoid products in leaves, providing proof that the in planta function(s) of VvCCD1 in photosynthetically active tissue is distinct from the in vitro activities demonstrated. The isolation and functional characterisation of VvCCD4a and VvCCD4b identify two additional CCDs that are functional in grapevine.ConclusionsTaken together, our results indicate that the three CCDs are under various levels of control that include gene expression (spatial and temporal), substrate specificity and compartmentalisation that act individually and/or co-ordinately to maintain carotenoid and volatile apocarotenoid levels in plants. Altering the expression of VvCCD1 in a transgenic grapevine population illustrated the divergence between the in vitro enzyme activity and the in planta activity of this enzyme, thereby contributing to the efforts to understand how enzymatic degradation of carotenoids involved in photosynthesis occurs. The identification and functional characterisation of VvCCD4a and VvCCD4b suggest that these enzymes are primarily responsible for catalysing the cleavage of plastidial carotenoids.

Dataset Information

The gene family-free median of three.

Publications

The gene family-free median of three.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets