Algolab at ICCABS 2018

ICCABS 2018 is the 8th edition of a series of well-established scientific conferences aiming to bring together leading academic and industry researchers to discuss the latest advances in computational methods for bio and medical sciences.
The 2018 edition was held in Las Vegas from Octtober, 18th through 20th of 2018.

Simone Ciccolella presented a talk:

  • gpps: an ILP-based approach for inferring cancer progressionwith mutation losses from single cell data

for which a preprint can be found here.

Algolab at Recomb 2018

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.

Detection of long noncoding (lncRNA) involved in RNA-Seq isoforms


  • Detection of long noncoding (lncRNA) involved in RNA-Seq isoformsHassan MahmoudDISCO, May 28, 2015 (slides).
    The recent discovery showed that the human and other mammalian genomes produce thousands of mRNA-like molecules namely, long noncoding RNAs (lncRNAs). Almost on a weekly basis, many biological studies detected that lncRNA is to be up or down-regulated in a particular disease. However, these lncRNAs which lack significant protein-coding capacity have been implicated in a wide range of biological functions through diverse and as yet poorly understood molecular mechanisms. The majority of human genes are alternatively spliced in a highly tissue and cell type–specific manner essential for generating protein diversity. The production of alternative splicing mRNAs is regulated by combinatorial use of multiple cis-acting RNA elements along the precursor mRNA (pre-mRNA). In this talk, I will show the concepts and subtypes of lncRNA, their role in gene regulation and their relation to alternative splicing, and the bioinformatics tools used for detecting lncRNA mainly from sequencing isoforms.


Covering pairs in directed acyclic graphs

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[1]-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.