A fast and scalable clustering-based approach for constructing reliable radiation hybrid maps

Raed I. Seetan, Anne M. Denton, Omar Al-Azzam, Ajay Kumar, M. Javed Iqbal, Shahryar Kianian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

The process of mapping markers from radiation hybrid mapping (RHM) experiments is equivalent to the traveling salesman problem and, thereby, has combinatorial complexity. As an additional problem, experiments typically result in some unreliable markers that reduce the overall quality of the map. We propose a clustering approach for addressing both problems efficiently by eliminating unreliable markers without the need for mapping the complete set of markers. Traditional approaches for eliminating markers use resampling of the full data set, which has an even higher computational complexity than the original mapping problem. In contrast, the proposed approach uses a divide and conquer strategy to construct framework maps based on clusters that exclude unreliable markers. Clusters are ordered using parallel processing and are then combined to form the complete map. Using an RHMdata set of the human genome, we compare the framework maps from our proposed approaches with published physical maps and with the Carthagene tool. Overall, our approach has a very low computational complexity and produces solid framework maps with good chromosome coverage and high agreement with the physical map marker order.

Original languageEnglish (US)
Title of host publicationProc. of the 12th Int. Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conj. with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013
PublisherAssociation for Computing Machinery
Pages34-41
Number of pages8
ISBN (Print)9781450323277
DOIs
StatePublished - 2013
Event12th Int.Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conjunction with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013 - Chicago, IL, United States
Duration: Aug 11 2013Aug 14 2013

Publication series

NameProc. of the 12th Int. Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conjunction with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013

Other

Other12th Int.Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conjunction with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013
CountryUnited States
CityChicago, IL
Period8/11/138/14/13

Keywords

  • Bioinformatics
  • Clustering
  • Framework mapping
  • Radiation hybrid mapping

Fingerprint Dive into the research topics of 'A fast and scalable clustering-based approach for constructing reliable radiation hybrid maps'. Together they form a unique fingerprint.

  • Cite this

    Seetan, R. I., Denton, A. M., Al-Azzam, O., Kumar, A., Iqbal, M. J., & Kianian, S. (2013). A fast and scalable clustering-based approach for constructing reliable radiation hybrid maps. In Proc. of the 12th Int. Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conj. with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013 (pp. 34-41). (Proc. of the 12th Int. Workshop on Data Mining in Bioinformatics, BIOKDD 2013 - Held in Conjunction with the 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, SIGKDD 2013). Association for Computing Machinery. https://doi.org/10.1145/2500863.2500868