Delishus: An efficient and exact algorithm for genome-wide detection of deletion polymorphism in autism

Derek Aguiar, Bjarni V. Halldórsson, Eric M. Morrow, Sorin Istrail*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Motivation: The understanding of the genetic determinants of complex disease is undergoing a paradigm shift. Genetic heterogeneity of rare mutations with deleterious effects is more commonly being viewed as a major component of disease. Autism is an excellent example where research is active in identifying matches between the phenotypic and genomic heterogeneities. A considerable portion of autism appears to be correlated with copy number variation, which is not directly probed by single nucleotide polymorphism (SNP) array or sequencing technologies. Identifying the genetic heterogeneity of small deletions remains a major unresolved computational problem partly due to the inability of algorithms to detect them. Results: In this article, we present an algorithmic framework, which we term DELISHUS, that implements three exact algorithms for inferring regions of hemizygosity containing genomic deletions of all sizes and frequencies in SNP genotype data. We implement an efficient backtracking algorithm-that processes a 1 billion entry genome-wide association study SNP matrix in a few minutes-to compute all inherited deletions in a dataset. We further extend our model to give an efficient algorithm for detecting de novo deletions. Finally, given a set of called deletions, we also give a polynomial time algorithm for computing the critical regions of recurrent deletions. DELISHUS achieves significantly lower false-positive rates and higher power than previously published algorithms partly because it considers all individuals in the sample simultaneously. DELISHUS may be applied to SNP array or sequencing data to identify the deletion spectrum for family-based association studies.

Original languageEnglish
Article numberbts234
Pages (from-to)i154-i162
Issue number12
Publication statusPublished - Jun 2012

Bibliographical note

Funding Information:
Funding: National Institute of Mental Health to Clara M. Lajonchere (PI) (Grant 1U24MH081810 to AGRE, partial); NIMH (1K23MH080954-05 to E.M.M.); Burroughs Wellcome Fund (to E.M.M., Career Award); National Science Foundation (Grant 1048831 to D.A., B.H. and S.I.)


Dive into the research topics of 'Delishus: An efficient and exact algorithm for genome-wide detection of deletion polymorphism in autism'. Together they form a unique fingerprint.

Cite this