Growing Directed Acyclic Graphs: Optimization Functions for Pathway Reconstruction Algorithms.

Area of Science:

• Molecular Systems Biology
• Computational Biology
• Bioinformatics

Background:

• Understanding how proteins transmit external signals to gene expression changes is a key challenge in molecular systems biology.
• Protein interaction networks are crucial for mapping cellular signaling pathways.
• Existing pathway databases may lack completeness, necessitating computational reconstruction methods.

Purpose of the Study:

• To develop a novel computational method for reconstructing biological signaling pathways.
• To address the challenge of identifying missing components in known pathway databases.
• To improve the accuracy and biological relevance of reconstructed signaling pathways.

Main Methods:

• Formulated a new pathway reconstruction problem based on iteratively growing directed acyclic graphs (DAGs).
• Developed an algorithm that guarantees optimal DAGs for defined cost functions.
• Applied and evaluated the algorithm on six diverse signaling pathways from the NetPath database.

Main Results:

• The proposed DAG-based method outperformed the existing k-shortest paths method in pathway reconstruction.
• Reconstructed pathways using the new method were enriched for distinct biological processes.
• Demonstrated the effectiveness of the DAG growing approach for pathway reconstruction.

Conclusions:

• Growing DAGs represent a promising advancement in computational pathway reconstruction.
• The method provides provably optimal pathways based on specific cost functions.
• This approach enhances the understanding of signaling mechanisms and identifies novel biological insights.