Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

The paralog-to-contig assignment problem

High quality gene models from fragmented assemblies
 
: Indrischek, Henrike; Wieseke, Nicolas; Stadler, Peter F.; Prohaska, Sonja J.

:
Fulltext (PDF; )

Algorithms for molecular biology. Online journal 11 (2016), Art. 1, 14 pp.
http://www.almob.org
ISSN: 1748-7188
English
Journal Article, Electronic Publication
Fraunhofer IZI ()
assignment problems; gene models; genome annotation; genome assembly; integer linear programming

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.

: http://publica.fraunhofer.de/documents/N-389308.html