Accurate Flow Decomposition via Robust Integer Linear Programming.

Area of Science:

• Bioinformatics
• Computer Science
• Computational Biology

Background:

• Minimum flow decomposition (MFD) is crucial for tasks like RNA transcript assembly.
• Existing MFD methods struggle with erroneous data common in bioinformatics.
• Current error handling focuses on individual edges, not solution paths.

Purpose of the Study:

• To develop a robust method for minimum flow decomposition that accounts for errors at the path level.
• To introduce a novel problem formulation addressing errors in bioinformatics applications.
• To improve the accuracy of flow decomposition in the presence of noisy data.

Main Methods:

• Interpreting flow decomposition as a robust optimization problem.
• Lifting error handling from individual edges to solution paths.
• Developing an Integer Linear Programming formulation for the new problem.

Main Results:

• The proposed formulation significantly improves error handling in flow decomposition.
• Experimental results show a 30-50% reduction in inaccuracy rate compared to previous methods.
• The method maintains practical computational requirements.

Conclusions:

• The new minimum path-error flow decomposition approach offers superior accuracy for bioinformatics.
• Robust optimization provides a more effective framework for handling errors in flow decomposition.
• This work advances computational methods for sequence assembly and related bioinformatics problems.