Heuristic shortest hyperpaths in cell signaling hypergraphs

Algorithms for Molecular Biology

Research

John Kececioglu¹  Spencer Krieger¹ 

[1] Department of Computer Science, The University of Arizona, 85721, Tucson, Arizona, USA;

关键词: Systems biology;    cell signaling networks;    reaction pathways;    directed hypergraphs;    shortest hyperpaths;    efficient heuristics;    hyperpath enumeration;   

DOI  :  10.1186/s13015-022-00217-9

 received in 2022-01-10, accepted in 2022-02-01,  发布年份 2022

来源: Springer

【 摘 要 】

BackgroundCell signaling pathways, which are a series of reactions that start at receptors and end at transcription factors, are basic to systems biology. Properly modeling the reactions in such pathways requires directed hypergraphs, where an edge is now directed between two sets of vertices. Inferring a pathway by the most parsimonious series of reactions corresponds to finding a shortest hyperpath in a directed hypergraph, which is NP-complete. The current state-of-the-art for shortest hyperpaths in cell signaling hypergraphs solves a mixed-integer linear program to find an optimal hyperpath that is restricted to be acyclic, and offers no efficiency guarantees.ResultsWe present, for the first time, a heuristic for general shortest hyperpaths that properly handles cycles, and is guaranteed to be efficient. We show the heuristic finds provably optimal hyperpaths for the class of singleton-tail hypergraphs, and also give a practical algorithm for tractably generating all source-sink hyperpaths. The accuracy of the heuristic is demonstrated through comprehensive experiments on all source-sink instances from the standard NCI-PID and Reactome pathway databases, which show it finds a hyperpath that matches the state-of-the-art mixed-integer linear program on over 99% of all instances that are acyclic. On instances where only cyclic hyperpaths exist, the heuristic surpasses the state-of-the-art, which finds no solution; on every such cyclic instance, enumerating all source-sink hyperpaths shows the solution found by the heuristic was in fact optimal.ConclusionsThe new shortest hyperpath heuristic is both fast and accurate. This makes finding source-sink hyperpaths, which in general may contain cycles, now practical for real cell signaling networks.AvailabilitySource code for the hyperpath heuristic in a new tool we call Hhugin (as well as for hyperpath enumeration, and all dataset instances) is available free for non-commercial use at http://hhugin.cs.arizona.edu.

【 授权许可】

CC BY   
© The Author(s) 2022. corrected publication 2022

【 图 表 】

Fig. 6

Fig. 1

Fig. 1

Fig. 5

12951_2022_1749_Article_IEq3.gif

Fig. 4

Fig. 3

Fig. 4

Fig. 3

12864_2022_9026_Article_IEq187.gif

Fig. 1

Fig. 1

Fig. 2

Fig. 7

Fig. 1

12951_2022_1749_Article_IEq1.gif

Fig. 2

12888_2022_4322_Article_IEq11.gif

12888_2022_4322_Article_IEq10.gif

Fig. 1

12888_2022_4322_Article_IEq9.gif

12888_2022_4322_Article_IEq8.gif

12888_2022_4322_Article_IEq7.gif

12888_2022_4322_Article_IEq6.gif

12888_2022_4322_Article_IEq5.gif

12888_2022_4322_Article_IEq4.gif

12888_2022_4322_Article_IEq3.gif

12864_2022_9026_Article_IEq170.gif

Fig. 1

Fig. 1

Fig. 1

Fig. 5

12936_2022_4393_Article_IEq6.gif

Fig. 1

Fig. 13

12888_2022_4322_Article_IEq2.gif

12888_2022_4322_Article_IEq1.gif

Fig. 1

Fig. 3

Fig. 3

Fig. 6

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 3

Fig. 1

Fig. 2

Fig. 1

Fig. 3

Fig. 1

Fig. 1

Fig. 1

Fig. 3

Fig. 2

Fig. 8

Fig. 1

Fig. 2

Fig. 5

Fig. 2

Fig. 1

Fig. 5

Fig. 3

Fig. 2

12864_2022_9026_Article_IEq102.gif

Fig. 2

Fig. 2

Fig. 7

Fig. 8

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 2

Fig. 4

Fig. 3

Fig. 3

Fig. 2

Fig. 1

12864_2022_9026_Article_IEq78.gif

Fig. 1

Fig. 2

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 3

Fig. 1

Fig. 4

Fig. 1

Scheme 1

Fig. 2

Fig. 3

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 2

Fig. 1

Fig. 1

Fig. 1

Fig.1

Fig. 1

Fig. 6

12864_2022_9026_Article_IEq59.gif

Fig. 1

12864_2022_9026_Article_IEq57.gif

Fig. 1

12864_2022_9026_Article_IEq55.gif

Fig. 3

Fig. 1

Fig. 4

Fig. 3

Fig. 6

41408_2022_764_Article_IEq31.gif

41408_2022_764_Article_IEq30.gif

41408_2022_764_Article_IEq28.gif

Fig. 1

41408_2022_764_Article_IEq26.gif

41408_2022_764_Article_IEq25.gif

41408_2022_764_Article_IEq24.gif

41408_2022_764_Article_IEq23.gif

41408_2022_764_Article_IEq22.gif

41408_2022_764_Article_IEq21.gif

41408_2022_764_Article_IEq19.gif

Fig. 2

Fig. 1

41408_2022_764_Article_IEq1.gif

Fig. 2

Fig. 5

Fig. 1

Fig. 1

40249_2022_1045_Article_IEq27.gif

Fig. 5

40249_2022_1045_Article_IEq25.gif

40249_2022_1045_Article_IEq24.gif

40249_2022_1045_Article_IEq23.gif

40249_2022_1045_Article_IEq22.gif

40249_2022_1045_Article_IEq21.gif

40249_2022_1045_Article_IEq20.gif

40249_2022_1045_Article_IEq17.gif

40249_2022_1045_Article_IEq16.gif

Fig. 1

40249_2022_1045_Article_IEq15.gif

40249_2022_1045_Article_IEq14.gif

40249_2022_1045_Article_IEq13.gif

40249_2022_1045_Article_IEq12.gif

40249_2022_1045_Article_IEq11.gif

40249_2022_1045_Article_IEq10.gif

40249_2022_1045_Article_IEq9.gif

40249_2022_1045_Article_IEq8.gif

40249_2022_1045_Article_IEq7.gif

40249_2022_1045_Article_IEq6.gif

Fig. 1

40249_2022_1045_Article_IEq1.gif

Fig. 4

Fig. 1

Fig. 1

Fig. 4

12864_2022_9026_Article_IEq26.gif

Fig. 3

Fig. 3

Fig. 3

Fig. 8

Fig. 2

Fig. 2

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 6

Fig. 8

Fig. 1

Fig. 2

Fig. 3

Fig. 6

Fig. 2

Fig. 3

Fig. 3

Fig. 3

Fig. 2

Fig. 2

Fig. 3

13731_2022_257_Article_IEq12.gif

Fig. 1

13731_2022_257_Article_IEq9.gif

13731_2022_257_Article_IEq7.gif

Fig. 2

Fig. 1

13731_2022_257_Article_IEq4.gif

Fig. 3

13731_2022_257_Article_IEq2.gif

Fig. 3

Fig. 1

Fig. 6

Fig. 5

Fig. 2

Fig. 2

Fig. 5

Fig. 1

Fig. 1

40708_2022_178_Article_IEq64.gif

Fig. 2

Fig. 1

Fig. 1

Fig.5

Fig. 5

Fig. 4

Fig. 2

Fig. 3

Fig. 5

40708_2022_178_Article_IEq53.gif

Fig. 2

Fig. 1

Fig. 6

Fig. 4

Fig. 1

Fig. 1

Fig. 6

40708_2022_178_Article_IEq35.gif

40517_2022_243_Article_IEq20.gif

Fig. 1

Fig. 3

Fig. 2

40517_2022_243_Article_IEq17.gif