Format

Send to

Choose Destination
Interdiscip Sci. 2019 Sep;11(3):397-411. doi: 10.1007/s12539-017-0267-y. Epub 2017 Nov 6.

A Novel Hypergraph-Based Genetic Algorithm (HGGA) Built on Unimodular and Anti-homomorphism Properties for DNA Sequencing by Hybridization.

Author information

1
Discrete Mathematics Research Laboratory, Srinivasa Ramanujan Centre, SASTRA University, Thanjavur, India.
2
School of Humanities and Sciences, SASTRA University, Thanjavur, India.
3
School of Computing, SASTRA University, Thanjavur, Tamilnadu, India. gangothri@sastra.ac.in.
4
School of Humanities and Sciences, SASTRA University, Thanjavur, India. gangothri@sastra.ac.in.
5
School of Computing, SASTRA University, Thanjavur, Tamilnadu, India.
6
Discrete Mathematics Research Laboratory, Srinivasa Ramanujan Centre, SASTRA University, Thanjavur, India. deankannan@sastra.edu.
7
School of Computing, SASTRA University, Thanjavur, Tamilnadu, India. deankannan@sastra.edu.
8
School of Humanities and Sciences, SASTRA University, Thanjavur, India. deankannan@sastra.edu.

Abstract

The sequencing by hybridization (SBH) of determining the order in which nucleotides should occur on a DNA string is still under discussion for enhancements on computational intelligence although the next generation of DNA sequencing has come into existence. In the last decade, many works related to graph theory-based DNA sequencing have been carried out in the literature. This paper proposes a method for SBH by integrating hypergraph with genetic algorithm (HGGA) for designing a novel analytic technique to obtain DNA sequence from its spectrum. The paper represents elements of the spectrum and its relation as hypergraph and applies the unimodular property to ensure the compatibility of relations between l-mers. The hypergraph representation and unimodular property are bound with the genetic algorithm that has been customized with a novel selection and crossover operator reducing the computational complexity with accelerated convergence. Subsequently, upon determining the primary strand, an anti-homomorphism is invoked to find the reverse complement of the sequence. The proposed algorithm is implemented in the GenBank BioServer datasets, and the results are found to prove the efficiency of the algorithm. The HGGA is a non-classical algorithm with significant advantages and computationally attractive complexity reductions ranging to [Formula: see text] with improved accuracy that makes it prominent for applications other than DNA sequencing like image processing, task scheduling and big data processing.

KEYWORDS:

Anti-homomorphism; Computational complexity; Genetic algorithm; Hypergraph; L-mers; Unimodular property

PMID:
29110287
DOI:
10.1007/s12539-017-0267-y

Supplemental Content

Full text links

Icon for Springer
Loading ...
Support Center