Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• RNA-Seq technology enables high-throughput transcript identification and quantification using short reads.
• Existing methods for genome-guided multi-assembly face challenges with complex transcript structures.

Purpose of the Study:

• To refine transcript assembly for RNA-Seq data by focusing on a bounded number of solution paths.
• To develop an efficient algorithm for the NP-hard problem of optimal transcript path finding.

Main Methods:

• Constructing a weighted directed acyclic graph (DAG) where vertices represent exons and arcs represent read alignments.
• Developing a dynamic programming algorithm with a runtime dependent on graph arc-width and the number of paths (k).
• Analyzing the fixed-parameter tractability (FPT) of the problem with respect to arc-width, maximum weight, and k.

Main Results:

• The problem of finding optimal transcript paths is NP-hard for many fitting functions.
• A dynamic programming algorithm achieves a runtime of O(W(k)⟨G⟩(k)(⟨G⟩+ k)n), demonstrating fixed-parameter tractability.
• The arc-width parameter is shown to be small for real and simulated RNA-Seq data.
• A fully polynomial-time approximation scheme (FPTAS) is developed for a specific fitting function.

Conclusions:

• The developed algorithm provides an efficient solution for transcript assembly in RNA-Seq analysis, particularly when a limited number of transcript paths are expected.
• The concept of arc-width is a valuable graph parameter for understanding the complexity of RNA-Seq assembly problems.
• The findings advance the computational methods for interpreting complex transcriptomes from high-throughput sequencing data.