Abstract We present FullSynesth , a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or syntenies , inside a species tree. The considered evolutionary model involves segmental events (i.e. acting on multiple genes) including duplications (D), losses (L), synteny fissions and transfers possibly going through unsampled or extinct species. Formally, given a set of syntenies in a set of genomes and a set $$\mathcal {G}$$ G of consistent gene trees for the gene families composing the syntenies, the problem is to infer a most parsimonious evolutionary history explaining the observed gene trees and syntenies given a species tree. The problem is known to be NP-hard for the DL distance. FullSynesth is based on Synesth explicating the evolution of a set of syntenies given a single synteny tree , which can be obtained from $$\mathcal {G}$$ G by selecting a given supertree. Rather than trying each supertree in turn, FullSynesth is based on a two-in-one approach simultaneously building and reconciling a synteny supertree . This algorithm runs in polynomial time for a fixed number of gene trees. We show on simulated datasets that FullSynesth significantly improves the running time of Synesth applied to each possible supertree. An implementation of the algorithm is available at: https://github.com/UdeM-LBIT/FullSynesth .

Abstract We present FullSynesth, a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or syntenies, inside a species tree. The considered evolutionary model involves segmental events (i.e. acting on multiple genes) including duplications (D), losses (L), synteny fissions and transfers possibly going through unsampled or extinct species. Formally, given a set of syntenies in a set of genomes and a set $$\mathcal {G}$$ G of consistent gene trees for the gene families composing the syntenies, the problem is to infer a most parsimonious evolutionary history explaining the observed gene trees and syntenies given a species tree. The problem is NP-hard for the DL distance. FullSynesth is based on Synesth explicating the evolution of a set of syntenies given a single synteny tree, which can be obtained from $$\mathcal {G}$$ G by selecting an “optimal” supertree. Rather than trying each supertree in turn, FullSynesth is based on a two-in-one approach simultaneously building and reconciling a synteny supertree. The running time of this algorithm is exponential in the number of gene trees rather than in the size of gene trees. We show on simulated datasets that FullSynesth significantly improves the running time of Synesth applied to each possible supertree. An implementation of the algorithm is available at: http://www.iro.umontreal.ca/~mabrouk/ .

MOTIVATION: It is largely established that all extant mitochondria originated from a unique endosymbiotic event integrating an α-proteobacterial genome into an eukaryotic cell. Subsequently, eukaryote evolution has been marked by episodes of gene transfer, mainly from the mitochondria to the nucleus, resulting in a significant reduction of the mitochondrial genome, eventually completely disappearing in some lineages. However, in other lineages such as in land plants, a high variability in gene repertoire distribution, including genes encoded in both the nuclear and mitochondrial genome, is an indication of an ongoing process of Endosymbiotic Gene Transfer (EGT). Understanding how both nuclear and mitochondrial genomes have been shaped by gene loss, duplication and transfer is expected to shed light on a number of open questions regarding the evolution of eukaryotes, including rooting of the eukaryotic tree. RESULTS: We address the problem of inferring the evolution of a gene family through duplication, loss and EGT events, the latter considered as a special case of horizontal gene transfer occurring between the mitochondrial and nuclear genomes of the same species (in one direction or the other). We consider both EGT events resulting in maintaining (EGTcopy) or removing (EGTcut) the gene copy in the source genome. We present a linear-time algorithm for computing the DLE (Duplication, Loss and EGT) distance, as well as an optimal reconciled tree, for the unitary cost, and a dynamic programming algorithm allowing to output all optimal reconciliations for an arbitrary cost of operations. We illustrate the application of our EndoRex software and analyze different costs settings parameters on a plant dataset and discuss the resulting reconciled trees. AVAILABILITY AND IMPLEMENTATION: EndoRex implementation and supporting data are available on the GitHub repository via https://github.com/AEVO-lab/EndoRex.

This has been an unusual year, even for ISMB. Due to the worldwide COVID-19 pandemic, the annual ISMB meeting (the 28th Annual Conference on Intelligent Systems for Molecular Biology), initially intended to be held in Montreal, Canada, was instead run as a fully virtual conference on July 13–16, 2020. A huge debt of gratitude is due to International Society for Computational Biology (ISCB) Executive Director Diane Kovats, Director of Conferences Steven Leard and the rest of the conference team for arranging to move the entire meeting online on extremely short notice! ISMB is the flagship conference of the ISCB and may be considered the world’s premier forum for dissemination of scientific research in computational biology. The Proceedings Track at ISMB provides an opportunity for members of the computational biology research community to submit full length papers featuring original research for thorough review. Both theoretical and applied submissions are welcomed in any field of computational biology; accepted papers appear in this special issue of Bioinformatics and are presented at the conference. The review process this year was managed by dividing the submitted manuscripts among nine scientific review areas. Program committee recruitment and reviewing were overseen by the Senior Program Committee (SPC), which includes the Proceedings Chairs and the nine sets of Area Chairs (AC), several of whom were nominated by the Communities of Special Interests (COSIs). Reviewers looked for novel, important biological insights; correctness; clarity and potential impact. Once reviews were submitted, papers with discrepant scores were discussed by the reviewers and the relevant ACs, often resulting in refined reviews and scores. Final acceptance decisions were made by the entire SPC, including the Proceedings Chairs listed as authors of this piece, plus the 18 ACs listed in Table 1. Thematic areas of ISMB2020 Notes: The table lists the ACs for each theme, the number of reviewed papers, the number of accepted papers and the acceptance rate for each area. The special area of General Computational Biology was designated to handle papers on emerging topics or those not fitting in any of the other areas. Thematic areas of ISMB2020 Notes: The table lists the ACs for each theme, the number of reviewed papers, the number of accepted papers and the acceptance rate for each area. The special area of General Computational Biology was designated to handle papers on emerging topics or those not fitting in any of the other areas. Eight of the reviewing areas in Table 1 focused on particular classes of biological problems, some of which are quite broad. The ninth area, General Computational Biology, is intended for submissions on emerging topics or those that do not fit well in other reviewing areas. Some more common topics of manuscripts handled by this area in 2020 included ontologies and bioNLP, single-cell methodologies, CRISPR and imaging applications. Some papers were moved between reviewing areas to avoid conflicts of interest. Abstracts, previously published papers, position papers, perspectives and reviews were not eligible for submission to the ISMB Proceedings track. In total, 329 manuscripts were submitted and sent out for review. We wish to especially acknowledge all 226 program committee members and 264 sub-reviewers for doing a tough job under adverse circumstances. Many of the world’s initial COVID-19 shutdown periods overlapped with the final weeks of the review period, yet the deadlines for reviewing and decision-making were met. Overall, we received a total of 1078 reviews, with an average of 3.3 reviews per submission. The distribution of the number of reviews per paper is shown in Figure 1. Nearly all manuscripts received at least three reviews; the average was 3.3 Conditional acceptance information was provided to the authors a month after the submission deadline and final acceptance of revised manuscripts was determined a month later. Overall, 65 manuscripts were accepted, for a final acceptance rate of 20%. The distribution of papers reviewed under the different thematic areas is shown in Table 1. The authors had the opportunity to designate the particular COSI session for which they believed their paper was most suitable. However, many of the submitted manuscripts made no specific COSI session request. Accordingly, accepted papers were first offered to the author-requested COSI if there was one, but the final assignments of accepted papers to COSI sessions were made by the COSI and Proceedings Chairs on the basis of both author and COSI requests. Three papers were assigned to the General Computational Biology session for presentation. The ultimate distribution of accepted papers to COSIs is shown in Table 2. COSI distribution of accepted ISMB 2020 Proceedings papers COSI distribution of accepted ISMB 2020 Proceedings papers We are grateful to the ISMB 2020 Steering Committee, Diane Kovats, Steven Leard, Pat Rodenburg and Seth Mulholland for their support, guidance and cheerful handling of both minor logistical questions and big existential ones at this difficult time. Special thanks go also to the SPC, the reviewers and their sub-reviewers, for going above and beyond in maintaining the high standards of ISMB on a time scale that would have been tight even under typical conditions. Thanks to the COSI chairs for great AC nominations, the ACs for being exceptionally responsive and professional and the COSI contacts for additional help during the process of identifying reviewers and in incorporating accepted papers into their programs. One of the bright spots in recent months has been the way the entire international research community has come together to focus on a common challenge. Data and code sharing have increased, journals have become more willing to consider manuscripts released as preprints, paywalls have been loosened and new collaborations have arisen. We see the ISMB community reflecting these trends, and we are heartened by the hope that some of these moves toward more open science will continue. Finally, we want to thank everyone who has participated in this conference–from keynote speakers to students attending for the first time. You make this meeting, and the whole ISMB community, what it is. We hereby invite you to read the papers in this Proceedings volume. Have a safe, healthy year and we hope to be able to welcome you in person to ISMB 2021 in Lyon, France.

The biennial joint meeting of ISMB (27th Annual Conference on Intelligent Systems for Molecular Biology) and ECCB (18th European Conference on Computational Biology) was held in Basel, Switzerland, July 21–25, 2019. ISMB is the flagship conference of the International Society for Computational Biology and the world’s premier forum for dissemination of scientific research in computational biology and its intersection with other areas. ECCB is similarly a top venue in the field, with a long tradition of publishing and presenting world-class research. This special issue serves as the Proceedings of ISMB/ECCB 2019. Following a successful model with a centralized manuscript review and acceptance process, this year’s conference organization provided the community with a unified submission interface for high-quality papers in the field of computational biology. The review process across 10 scientific areas was supervised by the Senior Program Committee (SPC), consisting of the Proceedings Chairs and Area Chairs (AC). About a third of the ACs were nominated by the Communities of Special Interests (COSIs), reflecting the desire of the ISMB/ECCB 2019 Steering Committee to involve COSIs in conference organization and the review process. Overall, the SPC consisted of 21 individuals; see Table 1. Thematic areas of ISMB/ECCB 2019 Note: The table lists the ACs for each theme, the number of reviewed papers, the number of accepted papers, and the acceptance rate for each area. A special area of General Computational Biology was created for papers not fitting in any of the predefined areas. Thematic areas of ISMB/ECCB 2019 Note: The table lists the ACs for each theme, the number of reviewed papers, the number of accepted papers, and the acceptance rate for each area. A special area of General Computational Biology was created for papers not fitting in any of the predefined areas. The scope of the conference includes theoretical papers, algorithms and statistical methods that allow for important novel biological insights and broadly defined intellectual contributions. We invited submission of papers in nine general scientific areas, organized by the relevant biological problems (Table 1). The 10th area of General Computational Biology was created to accommodate innovation outside of specified fields. The papers submitted to this area were largely in Text Mining, Mass Spectrometry and Visualization subfields, indicating community interest in these areas. All papers submitted to all areas were expected to present methodological and scientific contributions to the specific areas of submission. Abstracts, previously published papers, position papers, perspectives and reviews are not eligible for submission to the ISMB/ECCB Proceedings track. In total, 366 papers were submitted—a 10.6% increase over ISMB 2018. Of these, 363 papers were sent to review, receiving 1303 reviews from 388 Program Committee members. This constitutes an average of 3.6 reviews per submission. Three submissions had two completed reviews, 175 had three, 157 had four, 24 had five and four submissions had six completed reviews. The conditional acceptance information was provided to the authors a month after the submission deadline and final acceptance conveyed in another month. Overall, 69 manuscripts were accepted for a final acceptance rate of 18.9%. The distribution of papers reviewed in different areas is shown in Table 1. As was the case in 2018, the authors had the opportunity to request that their accepted manuscripts be presented in one of the COSI sessions. The most requests were made for MLCSB (64), followed by NetBio (39), Evolution (37), RegSys (37), TransMed (34), HiTSeq (33), Function (30), Microbiome (18), VarI (16), RNA (15), Text Mining (11), BioVis (10), Bio-Ontologies (7), CAMDA (4), Education (2) and CompMS (2). A further 35% of the submitted manuscripts made no specific COSI session request. Final assignments to COSI sessions were made by the Proceedings Chairs on the basis of the author and COSI requests. Three papers were assigned to the General Computational Biology session for presentation. The distribution of accepted papers to COSIs is shown in Table 2. Distribution of ISMB/ECCB 2019 Proceedings papers to COSIs Distribution of ISMB/ECCB 2019 Proceedings papers to COSIs We thank the ISMB/ECCB 2019 Steering Committee for their support and guidance. Special thanks go to the SPC and reviewers for their fantastic work dedicated to maintaining the high-quality standards of ISMB/ECCB in a compressed time frame. We are particularly grateful to Steven Leard, Diane Kovats and Pat Rodenburg for world-class organizational support. We would also like to thank the COSIs for nominating the ACs and the COSI contacts for their help in identifying reviewers and incorporating accepted papers into their programs. Finally, we thank the community for their interest and engagement in this conference—ISMB/ECCB 2019 belongs to you! With this, we invite you to read the Proceedings of ISMB/ECCB 2019. See you next year in Montreal, Canada, for ISMB 2020. Conflict of Interest: none declared.

The supertree problem asking for a tree displaying a set of consistent input trees has been largely considered for the reconstruction of species trees. Here, we rather explore this framework for the sake of reconstructing a gene tree from a set of input gene trees on partial data. In this perspective, the phylogenetic tree for the species containing the genes of interest can be used to choose among the many possible compatible "supergenetrees", the most natural criteria being to minimize a reconciliation cost. We develop a variety of algorithmic solutions for the construction and correction of gene trees using the supertree framework. A dynamic programming supertree algorithm for constructing or correcting gene trees, exponential in the number of input trees, is first developed for the less constrained version of the problem. It is then adapted to gene trees with nodes labeled as duplication or speciation, the additional constraint being to preserve the orthology and paralogy relations between genes. Then, a quadratic time algorithm is developed for efficiently correcting an initial gene tree while preserving a set of "trusted" subtrees, as well as the relative phylogenetic distance between them, in both cases of labeled or unlabeled input trees. By applying these algorithms to the set of Ensembl gene trees, we show that this new correction framework is particularly useful to correct weakly-supported duplication nodes. The C++ source code for the algorithms and simulations described in the paper are available at https://github.com/UdeM-LBIT/SuGeT.

Due to the key role played by gene trees and species phylogenies in biological studies, it is essential to have as much confidence as possible on the available trees. As phylogenetic tools are error-prone, it is a common task to use a correction method for improving an initial tree. Various correction methods exist. In this paper we focus on those based on the Duplication-Loss reconciliation model. The polytomy resolution approach consists in contracting weakly supported branches and then refining the obtained non-binary tree in a way minimizing a reconciliation distance with the given species tree. On the other hand, the supertree approach takes as input a set of separated subtrees, either obtained for separared orthology groups or by removing the upper branches of an initial tree to a certain level, and amalgamating them in an optimal way preserving the topology of the initial trees. The two classes of problems have always been considered as two separate fields, based on apparently different models. In this paper we give a unifying view showing that these two classes of problems are in fact special cases of a more general problem that we call LabelGTC, whose input includes a 0-1 edge-labelled gene tree to be corrected. Considering a tree as a set of triplets, we also formulate the TripletGTC Problem whose input includes a set of gene triplets that should be preserved in the corrected tree. These two general models allow to unify, understand and compare the principles of the duplication-loss reconciliation-based tree correction approaches. We show that LabelGTC is a special case of TripletGTC. We then develop appropriate algorithms allowing to handle these two general correction problems.

MOTIVATION: Codon reassignments have been reported across all domains of life. With the increasing number of sequenced genomes, the development of systematic approaches for genetic code detection is essential for accurate downstream analyses. Three automated prediction tools exist so far: FACIL, GenDecoder and Bagheera; the last two respectively restricted to metazoan mitochondrial genomes and CUG reassignments in yeast nuclear genomes. These tools can only analyze a single genome at a time and are often not followed by a validation procedure, resulting in a high rate of false positives. RESULTS: We present CoreTracker, a new algorithm for the inference of sense-to-sense codon reassignments. CoreTracker identifies potential codon reassignments in a set of related genomes, then uses statistical evaluations and a random forest classifier to predict those that are the most likely to be correct. Predicted reassignments are then validated through a phylogeny-aware step that evaluates the impact of the new genetic code on the protein alignment. Handling simultaneously a set of genomes in a phylogenetic framework, allows tracing back the evolution of each reassignment, which provides information on its underlying mechanism. Applied to metazoan and yeast genomes, CoreTracker significantly outperforms existing methods on both precision and sensitivity. AVAILABILITY AND IMPLEMENTATION: CoreTracker is written in Python and available at https://github.com/UdeM-LBIT/CoreTracker. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Polytomies in gene trees are multifurcated nodes corresponding to unresolved parts of the tree, usually due to insufficient differentiation between sequences of homologous gene copies. Apart from gene sequences, other information such as that contained in the species tree can be used to resolve such intricate parts of a gene tree. The problem of resolving a multifurcated tree has been considered by many authors, the objective function often being the number of duplications and losses reflected by the reconciliation of the resolved gene tree with the species tree. Here, we present PolytomySolver, an algorithm accounting for a more general model allowing different costs for duplications and losses per species. The time complexity of this algorithm is linear for the unit cost and is quadratic for the general cost, which outperforms the best known solutions so far by a linear factor. We show on simulated trees that the gain in theoretical complexity has a real practical impact on running times.

Combining a set of trees on partial datasets into a single tree is a classical method for inferring large phylogenetic trees. Ideally, the combined tree should display each input partial tree, which is only possible if input trees do not contain contradictory phylogenetic information. The simplest version of the supertree problem is thus to state whether a set of trees is compatible, and if so, construct a tree displaying them all. Classically, supertree methods have been applied to the reconstruction of species trees. Here we rather consider reconstructing a super gene tree in light of a known species tree S. We define the supergenetree problem as finding, among all supertrees displaying a set of input gene trees, one supertree minimizing a reconciliation distance with S. We first show how classical exact methods to the supertree problem can be extended to the supergenetree problem. As all these methods are highly exponential, we also exhibit a natural greedy heuristic for the duplication cost, based on minimizing the set of duplications preceding the first speciation event. We then show that both the supergenetree problem and its restriction to minimizing duplications preceding the first speciation are NP-hard to approximate within a n1-ϵ factor, for any 0 < ϵ < 1. Finally, we show that a restriction of this problem to uniquely labeled speciation gene trees, which is relevant to many biological applications, is also NP-hard. Therefore, we introduce new avenues in the field of supertrees, and set the theoretical basis for the exploration of various algorithmic aspects of the problems.

MOTIVATION: Large-scale methods for inferring gene trees are error-prone. Correcting gene trees for weakly supported features often results in non-binary trees, i.e. trees with polytomies, thus raising the natural question of refining such polytomies into binary trees. A feature pointing toward potential errors in gene trees are duplications that are not supported by the presence of multiple gene copies. RESULTS: We introduce the problem of refining polytomies in a gene tree while minimizing the number of created non-apparent duplications in the resulting tree. We show that this problem can be described as a graph-theoretical optimization problem. We provide a bounded heuristic with guaranteed optimality for well-characterized instances. We apply our algorithm to a set of ray-finned fish gene trees from the Ensembl database to illustrate its ability to correct dubious duplications. AVAILABILITY AND IMPLEMENTATION: The C++ source code for the algorithms and simulations described in the article are available at http://www-ens.iro.umontreal.ca/~lafonman/software.php. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Reconciled gene trees yield orthology and paralogy relationships between genes. This information may however contradict other information on orthology and paralogy provided by other footprints of evolution, such as conserved synteny. RESULTS: We explore a way to include external information on orthology in the process of gene tree construction. Given an initial gene tree and a set of orthology constraints on pairs of genes or on clades, we give polynomial-time algorithms for producing a modified gene tree satisfying the set of constraints, that is as close as possible to the original one according to the Robinson-Foulds distance. We assess the validity of the modifications we propose by computing the likelihood ratio between initial and modified trees according to sequence alignments on Ensembl trees, showing that often the two trees are statistically equivalent. AVAILABILITY: Software and data available upon request to the corresponding author.

BACKGROUND: The "small phylogeny" problem consists in inferring ancestral genomes associated with each internal node of a phylogenetic tree of a set of extant species. Existing methods can be grouped into two main categories: the distance-based methods aiming at minimizing a total branch length, and the synteny-based (or mapping) methods that first predict a collection of relations between ancestral markers in term of "synteny", and then assemble this collection into a set of Contiguous Ancestral Regions (CARs). The predicted CARs are likely to be more reliable as they are more directly deduced from observed conservations in extant species. However the challenge is to end up with a completely assembled genome. RESULTS: We develop a new synteny-based method that is flexible enough to handle a model of evolution involving whole genome duplication events, in addition to rearrangements, gene insertions, and losses. Ancestral relationships between markers are defined in term of Gapped Adjacencies, i.e. pairs of markers separated by up to a given number of markers. It improves on a previous restricted to direct adjacencies, which revealed a high accuracy for adjacency prediction, but with the drawback of being overly conservative, i.e. of generating a large number of CARs. Applying our algorithm on various simulated data sets reveals good performance as we usually end up with a completely assembled genome, while keeping a low error rate. AVAILABILITY: All source code is available at http://www.iro.umontreal.ca/~mabrouk.

BACKGROUND: Reconciliation is the classical method for inferring a duplication and loss history from a set of extant genes. It is based upon the notion of embedding the gene tree into the species tree, the incongruence between the two indicating evidence for duplication and loss. However, results obtained by this method are highly dependent upon the considered species and gene trees. Thus, painstaking attention has been given to the development of methods for reconstructing accurate gene trees. RESULTS: This paper highlights the fact that errors in gene trees are not the only reasons for the inference of an erroneous duplication-loss history. More precisely, we prove that, under certain reasonable hypotheses based on the widely accepted link between function and sequence constraints, even a well-supported gene tree yield a reconciliation that does not correspond to the true history. We then provide the theoretical underpinnings for a conservative approach to infer histories given such gene trees. We apply our method to the mammalian interleukin-1 (IL) gene tree, that has been used as a model example to illustrate the role of reconciliation.

BACKGROUND: Tandemly Arrayed Gene (TAG) clusters are groups of paralogous genes that are found adjacent on a chromosome. TAGs represent an important repertoire of genes in eukaryotes. In addition to tandem duplication events, TAG clusters are affected during their evolution by other mechanisms, such as inversion and deletion events, that affect the order and orientation of genes. The DILTAG algorithm developed in 1 makes it possible to infer a set of optimal evolutionary histories explaining the evolution of a single TAG cluster, from an ancestral single gene, through tandem duplications (simple or multiple, direct or inverted), deletions and inversion events. RESULTS: We present a general methodology, which is an extension of DILTAG, for the study of the evolutionary history of a set of orthologous TAG clusters in multiple species. In addition to the speciation events reflected by the phylogenetic tree of the considered species, the evolutionary events that are taken into account are simple or multiple tandem duplications, direct or inverted, simple or multiple deletions, and inversions. We analysed the performance of our algorithm on simulated data sets and we applied it to the protocadherin gene clusters of human, chimpanzee, mouse and rat. CONCLUSIONS: Our results obtained on simulated data sets showed a good performance in inferring the total number and size distribution of duplication events. A limitation of the algorithm is however in dealing with multiple gene deletions, as the algorithm is highly exponential in this case, and becomes quickly intractable.

MOTIVATION: The diversity of a haplotype, represented as a string of polymorphic sites along a DNA sequence, increases exponentially with the number of sites if recombinations are taking place. Reconstructing the history of recombinations compared with that of the polymorphic sites is thus extremely difficult. However, in the human genome, because of the relatively simple pattern of haplotype diversity dominated by a few ancestral haplotypes, the complexity of the recombinational network can be reduced, thus making its reconstruction feasible. We focus on the problem of inferring the recombination pathways starting with putative ancestral haplotypes and leading to new rare recombinant haplotypes. RESULTS: We describe classes of recombinations that represent the whole set of minimal recombination pathways leading to a new haplotype. We present an O(n(2)) algorithm that outputs such representative recombination pathways. We apply it to haplotypes of the 8 kb dystrophin gene segment dys44. AVAILABILITY: A software implementing the algorithm and some other extentions has been developed on a Java platform (JDK 1.3.1). It is freely available at http://www.iro.umontreal.ca/~mabrouk/

The genome can be modeled as a set of strings (chromosomes) of distinguished elements called genes. Genome duplication is an important source of new gene functions and novel physiological pathways. Originally (ancestrally), a duplicated genome contains two identical copies of each chromosome, but through the genomic rearrangement mutational processes of reciprocal translocation (prefix and/or suffix exchanges between chromosomes) and substring reversals, this simple doubled structure is disrupted. At the time of observation, each of the chromosomes resulting from the accumulation of rearrangements can be decomposed into a succession of conserved segments, such that each segment appears exactly twice in the genome. We present 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. Somewhat different techniques are required for a translocations-only model, a translocations/reversals model, both of these in the multichromosomal context (eukaryotic nuclear genomes), and a reversals-only model for single chromosome prokaryotic and organellar genomes. We apply these methods to the yeast genome, which is thought to have doubled, and to the liverwort mitochondrial genome, whose duplicate genes are unlikely to have arisen by genome doubling.

Several methods have been developed for identifying more or less complex RNA structures in a genome. Whatever the method is, it is always based on the search of conserved primary and secondary structures. While various efficient methods have been developed for searching motifs of the primary structure, usually represented as regular expressions, few effort has been expended in the efficient search of secondary structure signals. By a helix, we mean a structure defined by a combination of sequence and folding constraints. We present a flexible algorithm that searches for all approximate matches of a helix in a genome. Helices are represented by special regular expressions, that we call secondary expressions. The method is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. The worst time complexity is O(rpn), where n is the size of the genome, p the size of the secondary expression, and r its number of union symbols. We present our results of searching for specific signals of the tRNA and RNase P RNA in two genomes.

Genome duplication is an important source of new gene functions and novel physiological pathways.In the course of evolution, the nucleotide sequences of duplicated genes tend to diverge through mutation, so that one copy loses function (and disappears from view) or develops a new function, encoding a distinct but similar product.Originally a duplicated genome contains two identical copies of each chromosome, but through reciprocal translocation, parallel linkage patterns between the two copies are disrupted.Eventually, all that can be detected are several chromosome segments of greater or lesser length (blocks), each of which appears twice in the genome, containing many paralogous genes in parallel orders.We present an exact algorithm for reconstructing the ancestral pm-doubling genome in polynomial time, minimizing in key cases the number of translocations required to derive the observed order and orientation of blocks along the present-day chromosomes.We apply this to the genome duplication which has been described for Saccharomyces cere- visiae.1 Genome duplication Perhaps the most spectacular cause of gene duplication is tetraploidization of the genome.Normally a lethal accident of meiosis or other reproductive step, if this doubling of the genome can be resolved in the organism and eventually fixed as a normalized diploid state in a population, it represents a simultaneous duplication of the entire genetic complement.It transcends other mechanisms for gene duplication in that not only is one copy of each gene free to evolve its own function, but it can evolve in concert with any 'DBpartement d'Informatique et de recherche op&ationnelle, Universitd de Montreal, CP 6128