RECOMB 2018 is the 22nd edition of a series of well-established scientific conferences bridging the areas of computational, mathematical, statistical and biological sciences. The 2018 edition was held in Paris from April, 21st through 24th of 2018, and was preceded by a series of satellite workshops on the 19th-20th of April.
Luca Denti and Murray Patterson presented posters at the main conference titled:
- ASGAL: Aligning RNA-Seq Data to a Splicing Graph to Detect Novel Alternative Splicing Events which won best poster award (link to this poster, and preprint), and
- HapCHAT: Adaptive haplotype assembly for efficiently leveraging high coverage in long reads (link to this poster, and preprint).
Simone Ciccolella and Murray Patterson also presented a talk, as well as a poster at the Recomb-CCB satellite meeting of Recomb, both titled:
- Inferring Cancer Progression from Single Cell Sequencing while allowing loss of mutations
for which a preprint can be found here.
Gianluca Della Vedova has given the invited talk Character-based Phylogeny Construction and its Application to Tumor Evolution at the special session on Algorithms for biology at Computability in Europe 2017 in Turku (Finland).
Covering pairs in directed acyclic graphs, Yuri Pirola, LATA 2014 (slides).
- The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths “covering” all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a single path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
Haplotype-based prediction of gene alleles using pedigrees and SNP genotypes, Yuri Pirola, ACM-BCB 2013 (slides).
- Computational methods for gene allele prediction have been proposed to substitute dedicated and expensive assays with cheaper in-silico analyses that operate on routinely collected data, such as SNP genotypes. Most of these methods are tailored to the needs and characteristics of human genetic studies where they achieve good prediction accuracy. However, genomic analyses are becoming increasingly important in livestock species too. For livestock species generally the underlying—usually quite large and complex—pedigree is known and available; this information is not fully exploited by current allele prediction methods.
In this work, we propose a new gene allele prediction method based on a simple, but robust, combinatorial formulation for the problem of discovering haplotype-allele associations. The inherent uncertainty of the haplotype inference process is reduced by taking into account the inheritance of gene alleles across the population pedigree while genotypes are phased. The accuracy of the method has been extensively evaluated on a representative real-world livestock dataset under several scenarios and choices of parameters. The median error rate ranged from 0.0537 to 0.0896, with an average of 0.0678; this is 21% better than another state-of-the-art prediction algorithm that does not use the pedigree information. The experimental results support the validity of the proposed approach and, in particular, of the use of pedigree information in gene allele predictions.
A fast and practical approach to genotype phasing and imputation on a pedigree with erroneous and incomplete information, Yuri Pirola, ICCABS 2012 (slides).
- This work proposes the Min-Recombinant Haplotype Configuration with Bounded Errors problem (MRHCE), which extends the original Min-Recombinant Haplotype Configuration formulation by incorporating two common characteristics of real data: errors and missing genotypes (including untyped individuals). We describe a practical algorithm for MRHCE that is based on a reduction to the Satisfiability problem (SAT) and exploits recent advances in the constraint programming literature. An experimental analysis demonstrates the soundness of our model and the effectiveness of the algorithm under several scenarios. The analysis on real data and the comparison with state-of-the-art programs reveals that our approach couples better scalability to large and complex pedigrees with the explicit inclusion of genotyping errors into the model. The software, released under the GNU General Public License, can be freely downloaded from this page.