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 their chromosomes. These duplications may be used as data to ``halve'' the genome, i.e., to reconstruct the ancestral genome at the moment of doubling, but the solution is often highly non-unique. To resolve this problem, we take account of outgroups, external reference genomes, to guide and narrow down the search. Results: We improve on a previous, computationally costly, "brute force" method by adapting the genome halving algorithm of El-Mabrouk and Sankoff so that it rapidly and accurately constructs an ancestor close the outgroups, prior to a local optimization heuristic. We apply this to reconstruct the pre-doubling ancestor of S. cerevisiae and C. glabrata, guided by the genomes of three other yeasts that diverged before the genome doubling event. We analyze the results in terms 1) of the minimum evolution criterion, 2) how close the genome halving result is to the final (local) minimum, and 3) how close the final result is to an ancestor manually constructed by an expert with access to additional information. We also visualize the set of reconstructed ancestors using classic multidimensional scaling to see what aspects of the doubling descendants and outgroups influence the similarities and differences among the reconstructions.

Keywords: algorithms genome halving rearrangements whole genome duplication yeast

Hide

---

Motivation: Tagging gene and gene product mentions in scientific text is an important initial step of literature mining. In this paper, we describe in details our gene mention tagger participated in BioCreative 2 challenge and analyze what contributes to its good performance. Our tagger is interesting because it is based on the conditional random fields model (CRF), the most prevailing method for the gene mention tagging task in BioCreative 2.Our tagger accomplished the highest F-scores among them and second over all. Moreover, we accomplished our results by mostly applying open source packages, making it easy to duplicate our results. Results: We first describe in details how we developed our CRF-based tagger. We designed a very high dimensional feature set that includes most of information that may be possibly relevant. We trained bi-directional CRF models with the same set of features, one applies forward parsing and the other backward, and integrated two models based on the likelihood scores and dictionary filtering. One of the most prominent factors that contribute to the good performance of our tagger is the integration of an additional backward parsing model. However, from the definition of CRF, it appears that a CRF model is symmetric and bi-directional parsing models will produce the same results. We show that due to different feature settings, a CRF model can be asymmetric and our feature setting for our tagger in BioCreative 2 not only produces different results but also give backward parsing models slight but constant advantage over forward parsing model for gene mention tagging. To fully explore the potential of integrating bi-directional parsing models, we applied different feature settings to generate many bi-directional parsing models and integrate them based on the likelihood scores. Experimental results show that this integrated model can achieve even higher F-score solely based on the training corpus for gene mention tagging.