title: The paralog-to-contig assignment problem: high quality gene models from fragmented assemblies.
abstract: BACKGROUND
  The accurate annotation of genes in newly sequenced genomes remains a challenge. Although sophisticated comparative pipelines are available, computationally derived gene models are often less than perfect. This is particularly true when multiple similar paralogs are present. The issue is aggravated further when genomes are assembled only at a preliminary draft level to contigs or short scaffolds. However, these genomes deliver valuable information for studying gene families. High accuracy models of protein coding genes are needed in particular for phylogenetics and for the analysis of gene family histories.
  
  
  RESULTS
  We present a pipeline, ExonMatchSolver, that is designed to help the user to produce and curate high quality models of the protein-coding part of genes. The tool in particular tackles the problem of identifying those coding exon groups that belong to the same paralogous genes in a fragmented genome assembly. This paralog-to-contig assignment problem is shown to be NP-complete. It is phrased and solved as an Integer Linear Programming problem.
  
  
  CONCLUSIONS
  The ExonMatchSolver-pipeline can be employed to build highly accurate models of protein coding genes even when spanning several genomic fragments. This sets the stage for a better understanding of the evolutionary history within particular gene families which possess a large number of paralogs and in which frequent gene duplication events occurred.
authors.affiliation: Computational EvoDevo Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany ; Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany ; Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany.
authors.forename: Henrike
authors.initials: H
authors.lastname: Indrischek
authors.affiliation: Parallel Computing and Complex Systems Group, Department of Computer Science, Universität Leipzig, Augustusplatz 10, 04109 Leipzig, Germany.
authors.forename: Nicolas
authors.initials: N
authors.lastname: Wieseke
authors.affiliation: Bioinformatics Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany ; Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany ; Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, 04103 Leipzig, Germany ; Fraunhofer Institute for Cell Therapy and Immunology, Perlickstraße 1, 04103 Leipzig, Germany ; Department of Theoretical Chemistry, University of Vienna, Währinger Straße 17, 1090 Vienna, Austria ; Center for non-coding RNA in Technology and Health, Grønegårdsvej 3, 1870 Frederiksberg C, Denmark ; Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM87501 USA.
authors.forename: Peter F
authors.initials: PF
authors.lastname: Stadler
authors.affiliation: Computational EvoDevo Group, Department of Computer Science, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany ; Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, 04107 Leipzig, Germany.
authors.forename: Sonja J
authors.initials: SJ
authors.lastname: Prohaska
keywords: Assignment problems; Gene models; Genome annotation; Genome assembly; Integer linear programming