Application of Max-SAT-based ATPG to optimal cancer therapy design

Area of Science:

• Computational Biology
• Bioinformatics
• Systems Biology

Background:

• Gene regulatory network failures underlie cancer and other diseases.
• Identifying these signaling pathway faults is crucial for effective cancer treatment.
• Current methods require improved fault identification and targeted drug selection.

Purpose of the Study:

• To present an extensible Max-SAT based automatic test pattern generation (ATPG) algorithm for cancer therapy.
• To utilize Boolean Satisfiability (SAT) and the stuck-at fault model for representing signaling faults.
• To enable efficient selection of the most effective drugs through weighted partial Max-SAT formulation.

Main Methods:

• Developed an extensible Max-SAT based automatic test pattern generation (ATPG) algorithm.
• Employed Boolean Satisfiability (SAT) and the stuck-at fault model to represent gene signaling faults.
• Utilized a weighted partial Max-SAT formulation for optimal drug selection.

Main Results:

• Demonstrated fault identification and drug selection capabilities through various use cases.
• Successfully identified testable faults and selected optimal drugs for single/multiple known faults.
• Achieved optimal drug selection for overall fault coverage in growth factor signaling pathways.
• Experimental results show the algorithm is flexible and provides exact solutions rapidly.

Conclusions:

• The proposed Max-SAT based ATPG algorithm offers a flexible and efficient approach to cancer therapy.
• It enables precise identification of signaling faults and selection of targeted drugs.
• The method holds promise for advancing personalized cancer treatment strategies.