ISSN 2348-313X (Print) International Journal of Life Sciences Research ISSN 2348-3148 (online) Vol. 8, Issue 2, pp: (11-13), Month: April - June 2020, Available at: www.researchpublish.com
Longest Path Algorithm and using it to Find Unknown Genome via Shotgun Sequencing Lee, Kin Seng Singapore, Malaysia lksark@hotmail.com
Abstract: This article talks about Long Path Algorithm and the potential of using it to identify unknown genome via Shotgun Sequencing method. The aim of finding the longest possible path in a graph is to find a path that can cover the longest possible travelling distance in a graph, from a known starting node to an unknown ending node. Inside the longest path, individual nodes can either re-occur or not re-occur. Keywords: Longest Path, Shotgun Sequencing, find unknown genome, Overlap Graph.
I. INTRODUCTION In contrast to shortest path algorithm, there is longest path algorithm. Longest path algorithm is to find the possible longest path in a graph by finding the longest possible travelling distance in a graph. Therefore, we may able to use Longest Path Algorithm to identify an unknown genome via Shotgun Sequencing method. This paper briefly talks about the working principle of the Longest Path Algorithm, without experimental figures. More information and Longest Path Algorithm coding please visit my website: http://www.algoonline.net/LongestPath/ Longest_Path_algorithm.htm.
II. BRIEF DESCRIPTION OF LONGEST PATH ALGORITHM WORKING PRINCIPLE The aim of finding the longest possible path in a graph is to find a path that can cover the longest possible travelling distance in a graph, from a known starting node to an unknown ending node. Inside a graph‟s longest path, individual nodes can be either occur once or multiple times. The coding between these two are only minor differences. Longest Path Algorithm coding is somewhat similar to Shortest Path Algorithm. However Longest Path Algorithm occasionally have path travelling in closed loops problem, causing total travelling distance become infinity and program freeze. Therefore, longest path programming will need to have additional coding to check do targeted destination node reoccur inside current node‟s longest path. The targeted destination node will not again add inside current node‟s longest path if found re-occurred. Shortest Path problem on the other hands will not have such dilemmas. Similar to shortest path, the sub-path of the longest path itself are also the longest path. The closed loops could be nodes next to each other; the loops could be numerous numbers of nodes that linked together in big circles. The later one is more difficult to be spotted by eye. A. Longest Path with repetitive nodes In some of the longest path problems, the individual nodes could be repetitive. Nodes are not distinct in the longest path. Some of the nodes occur multiple times in the longest path. One of the examples is genome sequences. When the same nodes reoccur twice in the path, it forms a closed loop path. Program can get caught inside the closed loop, keep-on circulating and getting infinity travelling distance, creating program logic error. Hence, our program needs to put these closed loop paths into separate queues to avoid program freeze.
Page | 11 Research Publish Journals