An “optimal” k-needle placement strategy and its application to guiding transbronchial needle aspirations

Abstract

This article addresses the problem of finding an “optimal” strategy for placing k biopsy needles, given a large number of possible initial needle positions. We consider two variations of the problem: (1) Calculate the smallest set of needles necessary to guarantee a successful biopsy; and (2) Given a number k, calculate k needles such that the probability of a successful biopsy is maximized. Note that “needle” is used as shorthand for the parameter vector that specifies the needle placement. Both problems are formulated in terms of two general, NP-hard optimization problems. Our k-needle placement strategy can be considered as “optimal” in the sense that we are able to formulate it as a known NP-hard problem for which it is believed (NP≠P conjecture) that no efficient algorithm exists that computes the optimal solution. In other words, our strategy is “optimal” with respect to the best approximative algorithm known for the respective NP-hard problem. For the second variation we have implemented an approximative algorithm that is guaranteed to be within a factor of≈0.63 of the exact solution. Given a number k, the algorithm calculates k sets of parameters, each set specifying the placement of a needle and the corresponding probability of success. The resulting probabilities show that our approach can provide valuable decision support for the physician in choosing how many needles to place and how to place them.

A typical example of a biopsy where the initial needle position is known approximately is a transbronchial needle aspiration (TBNA). We demonstrate how our “optimal” needle placement strategy can be used to achieve sensor-less guidance of TBNA. The basic idea is to use a patient-specific model of the tracheobronchial tree (from CT/MR) and our model for flexible endoscopes to preoperatively estimate the unknown position of the bronchoscope. The result is a set of candidate shapes for the unknown shape of the bronchoscope before needle placement or, in other words, a (large) number of possible initial needle positions. By parameterizing the handling of the bronchoscope, including the insertion of the biopsy needle, we are able to apply our “optimal” strategy. The result is a TBNA protocol that, if executed during the procedure, prescribes how to handle the bronchoscope to maneuver the needle into the target. With the aforementioned endoscope model, we present a new way of modeling long, flexible instruments. The algorithm requires no initialization or preprocessing and calculates the workspace of an instrument based on its insertion depth and a set of internal and external constraints.

• Bronchoscopy
• needle biopsy
• transbronchial needle aspiration
• TBNA
• endoscope model
• set-covering problem
• virtual endoscopy