We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details

Leach, Adam, Rudden, Lucas S.P., Bond-Taylor, Sam, Brigham, John C., Degiacomi, Matteo T. & Willcocks, Chris G. (2020), Shape tracing: An extension of sphere tracing for 3D non-convex collision in protein docking, 2020 IEEE 20th International Conference on Bioinformatics and Bioengineering (BIBE) 2020 IEEE 20th International Conference on Bioinformatics and Bioengineering (BIBE). 49-52.

Author(s) from Durham


—This paper presents an algorithm, similar to implicit
sphere tracing, that ray marches 3D non-convex shapes for
efficient collision detection. Instead of finding points on the
surface where individual rays strike, an entire shape is marched
in unison by a lower bound of the boundary distance, calculated
at the closest point between the two surfaces. Advancing one
shape towards the other by this new bound allows us to identify
a contact in few steps. This method supports arbitrary nonconvex shapes, and can be run in parallel. We apply this to
protein-protein docking and show that we can identify around
80 docking poses per second featuring contact but no overlap,
irrespective of proteins’ specific geometry. This paves the way
to future fast docking algorithms, building upon implicit surface
representations to quickly find a well-distributed subset of close
candidate solutions for further investigation.