Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Transcript Abundance Estimation and the Laminar Packing Problem
verfasst von : Atif Rahman, Lior Pachter
Erschienen in: Algorithms for Computational Biology
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The expectation-maximization (EM) algorithm, or a streaming version of it, is widely used to resolve ambiguity during transcript abundance estimation from RNA-seq reads. The streaming algorithm is fast and memory efficient but its accuracy can depend on the order of the reads, which can be stabilized if a tree can be constructed to capture the ambiguity structure. Motivated by this, the laminar packing problem is introduced, which is proved to be NP-hard. Hardness of approximation and approximability results are also provided. Finally, an integer linear programming (ILP) formulation and a greedy approach are applied to real data from the human transcriptome to demonstrate that large instances can be solved in practice.