Invited Session Wed.2.MA 376

Wednesday, 13:15 - 14:45 h, Room: MA 376

Cluster 12: Life sciences & healthcare [...]

(Next generation) sequences


Chair: Gunnar W. Klau and Alexander Schönhuth



Wednesday, 13:15 - 13:40 h, Room: MA 376, Talk 1

Stefan Canzar
Transcriptome reconstruction using delayed column generation

Coauthors: Sandro Andreotti, Gunnar Klau, Knut Reinert, David Weese


Through alternative splicing, fragments of an RNA transcript of a gene, the exons, are recombined in different ways to generate different mRNA molecules, which in turn code for proteins. Determining the set of transcript variants and their abundance from millions of short sequence reads from the RNA complement of a cell is referred to as the transcriptome reconstruction problem. The main difficulty is that different mRNA variants transcribed from the same gene may share a considerable fraction as a common subsequence. Deciding from which variant a short read originates can thus be intricate and has to be done interdependently, based on the global information provided by high-throughput transcriptome sequencing data.
We present an algorithm that implicitly explores the entire space of all possible transcriptomes by using a delayed column generation approach. We show that the prizing problem is a variant of the longest path problem in directed acyclic graphs, which we can solve efficiently.



Wednesday, 13:45 - 14:10 h, Room: MA 376, Talk 2

Tobias Marschall
CLEVER: Clique-enumerating variant finder

Coauthors: Markus Bauer, Stefan Canzar, Ivan Costa, Gunnar W. Klau, Alexander Schliep, Alexander Schönhuth


Next-generation sequencing techniques have for the first time facilitated a large scale analysis of human genetic variation. However, despite the advances in sequencing speeds, achieved at ever lower costs, the computational discovery of structural variants is not yet standard. It is likely that a considerable amount of variants have remained undiscovered in many sequenced individuals. Here we present a novel internal segment size based approach, which organizes all, including also concordant reads into a read alignment graph where max-cliques represent maximal contradiction-free groups of alignments. A specifically engineered algorithm then enumerates all max-cliques and statistically evaluates them for their potential to reflect insertions or deletions (indels). We achieve highly favorable performance rates in particular on indels of sizes 30-500 bp and predict a considerable amount of correct, but so far undiscovered variants.



Wednesday, 14:15 - 14:40 h, Room: MA 376, Talk 3

Susanne Pape
Computational complexity of the multiple sequence alignment problem

Coauthor: Alexander Martin


During the last decades, continuing advances in molecular bioinformatics (for example the Human Genome Project) have led to increased information about biological sequences like protein or DNA sequences. Multiple alignments of these sequences play an important role in detecting conserved subregions, inferring evolutionary history, or predicting protein structure and function.
We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment - two problems that have indeed received much attention in biological sequence comparison.
From a mathematical point of view, both problems are difficult to solve and often remain hard, even if we restrict the problems to instances with scoring matrices that are a metric, a binary alphabet, or a gap-0-alignment (i.e. sequences can be shifted relative to each other, but no internal gaps are allowed).
Here, we give an overview of some recent results about NP-completeness and Max-SNP-hardness, analyze the computational complexity of some restricted versions of this problem, and present some new complexity and approximation results.


  Today, Ohio Payday Loans are legitimate, but there are illegal transactions that are still on the rise. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.