返回Google圖書搜尋

Graph Algorithms for Assembling Integrated Genome Maps [microform]

出版	Thesis (Ph.D.)--University of Toronto, 2003
ISBN	06127831899780612783188
URL	http://books.google.com.hk/books?id=_Jx9tgAACAAJ&hl=&source=gbs_api

註釋The methods and algorithms are tested on human genome mapping data and also on simulated data. The results from applying our structure graph algorithm to Sequenced Tag Site (STS) mapping data reveal a network-like pattern where linear segments often correlate with data from continuous pieces (contigs) of the genome. The underlying interval graph nature of the probe mapping data is thus revealed, thereby facilitating identification and extraction of contigs. Results from the application of our "virtual probe" technique for integrating probe and overlap data indicate that this method can produce longer double-linkage contigs than STS probes alone, and that it provides a new way of assessing overlap data. Results of experiments on enumeration of cliques in large, sparse graphs representing genome mapping data show that our modification of the Bron-Kerbosch algorithm requires time which is approximately linear in the number of vertices, whereas other tested algorithms had worse than linear time complexity. Results from tests of the clustering algorithm on simulated noisy overlap data indicate that it effectively counters the increase in clique numbers caused by false negatives.