Exhaustive Search Meets DNA Sequencing: A Comprehensive Review of TSP-Based Approaches

Year : 2024 | Volume : 02 | Issue : 02 | Page : 11 21
    By

    Impana G.B.,

  • Pallavi M. Jhadav,

  • Mohammad Raffi,

  1. Student, Department of Computer Science and Engineering, University B.D.T College of Engineering, Davanagere, Karnataka, India
  2. Student, Department of Computer Science and Engineering, University B.D.T College of Engineering, Davanagere, Karnataka, India
  3. Student, Department of Computer Science and Engineering, University B.D.T College of Engineering, Davanagere, Karnataka, India

Abstract

Exhaustive search is a highly computational complex algorithm that checks every possibility to obtain the best solution. We illustrate an exhaustive search by applying it to three important problems: the traveling salesman problem, the knapsack problem, and the assignment problem. In this paper, we took a traveling salesman problem to explain DNA Sequencing. Since traveling salesman problem is an algorithmic problem that finds the shortest route between a set of points or locations that must be visited. Traveling salesman problem can be used to solve DNA sequencing problems by applying DNA computing. DNA sequencing is a crucial process in modern genetics. Traditional methods are often time-consuming and computationally expensive. This study proposes a novel approach to DNA sequencing by framing the problem as a traveling salesman problem. By leveraging efficient traveling salesman problem solvers, we reconstruct the original DNA sequence from fragmented reads. Our approach, traveling salesman problem-Seq, models the DNA sequencing problem as a weighted graph, where nodes represent reads and edges represent overlap between reads. The traveling salesman problem solver finds the shortest Hamiltonian cycle, corresponding to the most likely DNA sequence. We demonstrate the traveling salesman problem-Seq’s effectiveness on simulated and real-world datasets.

Keywords: DNA sequencing, travelling salesman problem, ant colony algorithm, gene therapy, organ transplant

[This article belongs to International Journal of Bioinformatics and Computational Biology ]

How to cite this article:
Impana G.B., Pallavi M. Jhadav, Mohammad Raffi. Exhaustive Search Meets DNA Sequencing: A Comprehensive Review of TSP-Based Approaches. International Journal of Bioinformatics and Computational Biology. 2024; 02(02):11-21.
How to cite this URL:
Impana G.B., Pallavi M. Jhadav, Mohammad Raffi. Exhaustive Search Meets DNA Sequencing: A Comprehensive Review of TSP-Based Approaches. International Journal of Bioinformatics and Computational Biology. 2024; 02(02):11-21. Available from: https://journals.stmjournals.com/ijbcb/article=2024/view=183905


Browse Figures

References

  1. Karl J. V. Nordström, Markus Sällman Almén, Monika M. Edstam, Robert Fredriksson, Helgi B. Schiöth, Independent HHsearch, Needleman–Wunsch-Based, and Motif Analyses Reveal the Overall Hierarchy for Most of the G Protein-Coupled Receptor Families, Molecular Biology and Evolution, Volume 28, Issue 9, September 2011, Pages 2471–2480
  2. Lappalainen T, Scott AJ, Brandt M, Hall IM. Genomic Analysis in the Age of Human Genome Sequencing. Cell. 2019 Mar 21;177(1):70-84.
  3. Sammeth et al. “Computational methods for sequencing and analyzing genomes.” Annual Review of Genomics and Human Genetics, 2013,14:455-476.
  4. T. Hoang et al. “Solving the traveling salesman problem with a hybrid genetic algorithm.” Journal of Heuristics, 2007, 13(1):77-94.
  5. Dorigo M, Gambardella LM, Middendorf M, Stutzle T. Guest editorial: special section on ant colony optimization. IEEE Transactions on Evolutionary Computation. 2002 Aug;6(4):317-9.
  6. Dong G, Guo WW, Tickle K. Solving the traveling salesman problem using cooperative genetic ant systems. Expert systems with applications. 2012 Apr 1;39(5):5006-11.
  7. Stützle T, Hoos HH. MAX–MIN ant system. Future generation computer systems. 2000 Jun 1;16(8):889-914.
  8. Dorigo M, Birattari M, Stutzle T. Ant colony optimization. IEEE computational intelligence magazine. 2006 Nov;1(4):28-39.
  9. Alaya I, Solnon C, Ghedira K. Ant colony optimization for multi-objective optimization problems. In19th IEEE international conference on tools with artificial intelligence (ICTAI 2007) 2007 Oct 29 (Vol. 1, pp. 450-457). IEEE.
  10. Colorni A, Dorigo M, Maniezzo V, Trubian M. Ant system for job-shop scheduling. JORBEL-Belgian Journal of Operations Research, Statistics, and Computer Science. 1994;34(1):39-53.
  11. Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE transactions on evolutionary computation. 2002 Aug;6(4):333-46.
  12. Roth AE, Sönmez T, Ünver MU. Kidney exchange. The Quarterly journal of economics. 2004 May 1;119(2):457-88.
  13. Abraham DJ, Blum A, Sandholm T. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. InProceedings of the 8th ACM conference on Electronic commerce 2007 Jun 11 (pp. 295-304).
  14. Cook WJ, Applegate DL, Bixby RE, Chvatal V. The traveling salesman problem: a computational study. Princeton university press; 2011 Dec 31.
  15. Dorigo M, Di Caro G. Ant colony optimization: a new meta-heuristic. InProceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406) 1999 Jul 6 (Vol. 2, pp. 1470-1477). IEEE.
  16. Schwartz DC, Waterman MS. New Generations: Sequencing Machines and Their Computational Challenges. J Comput Sci Technol. 2010 Jan 1;25(1):3-9.
  17. Ejigu GF, Jung J. Review on the Computational Genome Annotation of Sequences Obtained by Next-Generation Sequencing. Biology (Basel). 2020 Sep 18;9(9):295.
Regular Issue Subscription Original Research
Volume 02
Issue 02
Received 10/09/2024
Accepted 07/10/2024
Published 18/11/2024
329


My IP

PlumX Metrics