Developing the Performance of Tiling Arrays

Developing the Performance of Tiling Arrays

Mohamed Abdelhamid Abbas (King Khalid University, Saudi Arabia)
Copyright: © 2013 |Pages: 11
DOI: 10.4018/978-1-4666-2653-9.ch010

Abstract

Genomic tiling arrays are able to inspect the genome of haphazard species for which the sequence is known. The plan of proper oligonucleotide probes for such arrays is computationally difficult if features such as oligonucleotide quality and recurring regions are considered. Prior works have developed the minimal tiling path problem for the choice of oligonucleotides using Dijkstra’s shortest path algorithm to compute universal finest tiling paths from millions of candidate oligonucleotides on computers. Although Dijkstra’s algorithm works well, it is complicated and may take a long time for routers to process it and the efficiency of the network fails. In this paper, the author discusses a search approach that can decrease the average complexity time of tilling arrays. This aspiration is realized by searching for the shortest path to the probes using a faster algorithm. This paper enhances A* Algorithm and exploits the enhanced version, called A**, instead of Dijkstra’s algorithm. The enhanced version is more efficient and can decrease the average time complexity, thus increasing the performance of tiling array.
Chapter Preview
Top

2. Prior Works

Prior works formulated the problem of finding the shortest path between the start oligonucleotide probe and the destination one as finding the shortest path in a graph as depicted in Figure 1. The set of vertices are the probes {v1, . . ., vn} with special nodes 0 and n + 1, which are virtual probes. It is required to tile before the start and after the end of the sequence. For an edge (va, vb), with va ≥1, vb ≤ n Where n is the total number of vertices in the graph. The total weight is computed as w(va, vb). The weights w(0, va) and w(va, n+1) are defined as d(0, va). Prior work depends to find the shortest path using Dikstra’s shortest path algorithm (Schliep & Krause, 2007; Dai, 2005). Another algorithm that find the shortest path is A* algorithm. It is an efficient more than Dikstra’s algorithm but its applications appears only in engineering science such as civil engineering, town planning and roads. The next subsections depict the structure and the behavior of these algorithms in details (Dai, 2005).

Complete Chapter List

Search this Book:
Reset