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. 2

Fig. 2

Fig. 5

Fig. 1

Fig. 1

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. 4

Fig. 1

Fig. 7

40708_2022_178_Article_IEq42.gif

Fig. 3

Fig. 6

40708_2022_178_Article_IEq39.gif

Fig. 6

Fig. 2

40708_2022_178_Article_IEq35.gif

40517_2022_243_Article_IEq20.gif

40517_2022_243_Article_IEq19.gif

Fig. 1

Fig. 4

Fig. 2

Fig. 3

40708_2022_178_Article_IEq25.gif

Fig. 2

Fig. 3

40517_2022_243_Article_IEq17.gif

40517_2022_243_Article_IEq16.gif

Fig. 2

Fig. 1

40708_2022_178_Article_IEq17.gif

Fig. 3

Fig. 5

Fig. 1

40517_2022_243_Article_IEq14.gif

Fig. 2

40517_2022_243_Article_IEq12.gif

40517_2022_243_Article_IEq11.gif

Fig. 1

12864_2022_9026_Article_IEq3.gif

Fig. 2

Fig. 4

Fig. 1

Fig. 2

Fig. 3

40517_2022_243_Article_IEq10.gif

Fig. 4

Fig. 9

Fig. 3

Fig. 3

Fig. 4

40517_2022_243_Article_IEq8.gif

Fig. 2

Fig. 3

Fig. 1

Fig. 3

Fig. 2

Fig. 3

40517_2022_243_Article_IEq5.gif

40517_2022_243_Article_IEq4.gif

Fig. 1

Fig. 7

Fig. 1

Fig. 2

Fig. 4

Fig. 4

40708_2022_178_Article_IEq7.gif

40517_2022_243_Article_IEq3.gif

Scheme 1

Fig. 2

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 7

Fig. 2

40517_2022_243_Article_IEq2.gif

40517_2022_243_Article_IEq1.gif

Fig. 1

Fig. 3

Fig. 4

Fig. 6

Fig. 4

12951_2022_1737_Article_IEq1.gif

Fig. 8

Fig. 2

Fig. 3

Fig. 4

Fig. 2

Fig. 4

Fig. 1

Fig. 3

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 2

Fig. 1

Fig. 2

Fig. 1

Fig. 4

Fig. 6

Fig. 1

Fig. 4

Fig. 4

Fig. 6

Fig. 3

Fig. 3

Fig. 1

Fig. 5

Fig. 1

Fig. 5

Fig. 3

Fig. 5

Fig. 1

Fig. 2

Fig. 4

Fig. 1

Fig. 3

Fig. 4

Fig.1

Fig. 1

Fig. 1

Fig. 3

Fig. 4

Fig. 1 (abstract P46).

Fig. 3

Fig. 1

Fig. 1

Fig. 4

Fig. 2

40560_2022_645_Article_IEq3.gif

40560_2022_645_Article_IEq2.gif

Scheme 1

Fig. 2

Fig. 1

Fig. 3

Fig. 1

Fig. 1

Fig. 13

Fig. 1

Fig. 2

Fig. 3

Fig. 7

Fig. 1

Fig. 6

Fig. 6

Fig. 11

Fig. 2

Fig. 9

Fig. 1

Fig. 4

12936_2022_4386_Article_IEq183.gif

Fig. 10

Fig. 7

Fig. 3

12936_2022_4386_Article_IEq179.gif

Fig. 4

Fig. 2

Fig. 2

Fig. 2

40644_2022_517_Article_IEq1.gif

Fig. 1

Fig. 1

12936_2022_4386_Article_IEq169.gif

Fig. 6

Fig. 1

Fig. 9

Fig. 5

Fig. 6

Fig. 1

Fig. 1

Fig. 1

Fig. 4

Fig. 8

Fig. 3

Fig. 7

Fig. 6

Fig. 1

Fig. 1

Fig. 3

12936_2022_4386_Article_IEq146.gif

Fig. 1

Fig. 2

Fig. 6

12936_2022_4386_Article_IEq142.gif

Fig. 1

Fig. 1

Fig. 1

Fig. 2

Fig. 2

Fig. 5

Fig. 1

Fig. 4

12936_2022_4386_Article_IEq132.gif

12902_2022_1222_Article_IEq2.gif

Fig. 7

Fig. 6

Fig. 4

Fig. 3

Fig. 2

Fig. 3

Fig. 5

13690_2022_1011_Article_IEq4.gif

13690_2022_1011_Article_IEq2.gif