pipette
ENEnglish

Exact and Efficient Methods for Identifying Carcinogenic Multi-Hit Gene Combinations

Rick S. H. Willemsen, Teresa L. F. Ho, Tenindra Abeywickrama

PreprintDice ser un gran avance

En palabras de los autores

Cancer is driven by an estimated two to nine gene mutations, known as multi-hit combinations. Due to the large number of genes, identifying these multi-hit combinations presents a computationally challenging problem, which has previously required supercomputers to enumerate all or most gene combinations. Recent work formulated this classification task as the Multi-Hit Cancer Driver Set Cover Problem (MHCDSCP) and solved it via column generation on a single commodity CPU, where a pricing problem identifies promising gene combinations (arXiv:2602.22551). The main bottleneck is the pricing problem that has to be solved repeatedly. To solve the pricing problem to optimality, we propose a dedicated depth first search method that enumerates all possible gene combinations. Although enumerating gene combinations with depth first search have been performed on supercomputers with around 150,000 CPU cores (arXiv:2603.16721), our depth first search algorithm solves the pricing problem to optimality within seconds on a single CPU by leveraging dual information to prune large parts of the search space. By eliminating this bottleneck, our approach yields the first exact method for the MHCDSCP, which is guaranteed to find a global optimal solution.

Resultado principalEl resumen no menciona limitaciones.

En palabras simples Resumen con IA

El cáncer se desarrolla a partir de dos a nueve mutaciones genéticas que actúan juntas, llamadas combinaciones de múltiples impactos. Encontrar estas combinaciones es computacionalmente difícil y antes necesitaba supercomputadoras. Los autores crearon un método de búsqueda en profundidad que resuelve el problema de precios clave de manera óptima. Su algoritmo se ejecuta en segundos en una sola CPU al usar información dual para podar el espacio de búsqueda. Esto produce el primer método exacto garantizado para encontrar una solución óptima global.

Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 13 pages