Arbeitsgruppenseminar Genominformatik


392188 Stoye Summer 2012 Thursday 16-18 in U10-146 ekvv

Course Description

In this seminar, current topics of the Genome Informatics research group are presented.

(In dieser Veranstaltung wird in Vorträgen über aktuelle Themen aus der Forschung der Arbeitsgruppe Genominformatik berichtet.)

Schedule

Date Topic Name
05.04.2012 Organization of the seminar Jens Stoye
12.04.2012 A Pseudo-Boolean programming approach to compute differences and similarities between two genomes. Annelyse Thévenin
19.04.2012 (Jens in Barcelona)
26.04.2012 Algorithmic Methods for Structural Variation Detection Iman Hajirasouliha
03.05.2012 (Jens in Bergen)
10.05.2012 (none)
17.05.2012 (Himmelfahrt)
24.05.2012 Tractability Results for the Consecutive-Ones Property with Multiplicity Roland Wittler
31.05.2012, 18s.t. Maximum Common Intervals Revisited Jens Stoye
07.06.2012 (Fronleichnam)
08.06.2012, 11s.t. Gene tree / species tree reconciliation with horizontal transfers Murray Patterson
14.06.2012 Power and limitations of DNA strand displacement systems Jan Manuch
15.06.2012, 11s.t. Comparison of metagenomic data by identifying enriched pathways in metabolic networks Yvonne Herrmann
21.06.2012 (Jens in Halle)
28.06.2012\\in room M3-115 MeTrans - Software platform for the analysis of metatranscriptomes Christina Ander
29.06.2012, 11s.t. Detect Metagenomic Association with Environmental Factor Xue Tian
05.07.2012 (Jens in Helsinki)
12.07.2012 BlastGraph\\Bachelor Kickoff-talks Guillaume Holley\\Pia Heitkämper, Julia Gierens
09.08.2012 The Genome Sequence of Sugar Beet (Beta vulgaris) and Intraspecific Variation Juliane Dohm
27.09.2012 T-cell (B-cell) receptor repertoire analysis using next-generation sequencing Pina Krell

Abstracts:

Algorithmic Methods for Structural Variation Detection
Iman Hajirasouliha

We discuss the challenges of detecting structural variations in sequenced genomes. We present our methods on finding deletions, novel sequence insertions, and mobile element insertions. We also present our recent approach: a shift in genomic structural variation (SV) studies away from the conventional two step approach of i) independent SV discovery and ii) pairwise comparison of structural variation to a simultaneous SV discovery framework in multiple genomes. Tests of our novel framework on the genomes of mother-father-child trios sequenced by Illumina show that the conventional strategy works poorly in providing meaningful biological results through comparative analysis. Our framework not only significantly reduces the number of incorrect de novo variations for the same number of total variations but also predicts more known true positives. We also present our results on the 1000 GP data and discuss the future directions.

Tractability Results for the Consecutive-Ones Property with Multiplicity
Roland Wittler

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1's in each row are consecutive. We consider here a variant of the C1P where columns can appear multiple times in the ordering. Although the general problem of deciding the C1P with multiplicity is NP-complete, we present a case of interest in comparative genomics that is tractable.

This is joint work with Cedric Chauve, Jan Manuch and Murray Patterson (all from Vancouver). The talk has been given by Murray at CPM 2011 in Palermo, Italy.

Power and limitations of DNA strand displacement systems
Jan Manuch

A DNA strand displacement systems (DSD systems) are widely-studied and useful models of molecular programming. These systems can perform only one type of reaction: “strand dispacement”, during which one short DNA strand (signal) replaces another short DNA strand attached to a long DNA strand (template). We first show that DSD systems can perform an exponentially long computations (in the volume of the molecules) by simulating Gray code binary counter. This is achieved by a heavy use of recycling: product of one reaction is a reactant in a later reaction, which has the benefits of reducing consumption, or waste, of molecules and of avoiding fuel depletion.

However, in order for our DSD binary counter and some DSD systems in the literature to behave in an expected manner, the initial number of copies of some reagents is required to be fixed. We show that, when multiple copies of all initial molecules are present, general types of DSD systems fail to work correctly if the length of the shortest sequence of reactions needed to produce any given molecule exceeds a threshold that grows polynomially with attributes of the system.

This is a joint work with Anne Condon, Alan Hu, Bonnie Kirkpatrick and Chris Thachuk.

The Genome Sequence of Sugar Beet (Beta vulgaris) and Intraspecific Variation
Juliane Dohm

Despite recent advances in sequencing technologies the assembly of genomes to high quality remains a challenge. The genome of sugar beet (Beta vulgaris) has an estimated size of 758 Mbp in nine chromosomes. We prepared a high-quality reference assembly from a doubled haploid sugar beet accession with data generated on Roche/454, Illumina, and Sanger platforms. Four additional breeding lines were sequenced de novo, and their genomes were compared to the reference sequence.