Parallel mesh algorithms for grid graph shortest paths with application to separation of touching chromosomes

The grid graph shortest path problem has many applications. In this paper, we present practical mesh algorithms using a local cost-reducing operation for various forms of the grid graph shortest path problem. The algorithms are very simple and can easily mark the vertices on shortest paths between any two vertices. The time complexity of the algorithm is proportional to the maximum length of the shortest paths with a very small multiplicative constant. Also in this paper, we discuss the application of the parallel algorithms in automatic chromosome analysis to intelligently split touching chromosomes. We identify local features useful for finding a potential path to separate touching chromosomes. We then define a distance measure based on the local features and find the best splitting path to cut touching chromosomes. The splitting algorithm only uses local information and is highly parallel.