Fast and accurate genome anchoring using fuzzy hash maps

John Healy; Desmond Chambers

doi:10.1007/978-3-642-19914-1_21

Fast and accurate genome anchoring using fuzzy hash maps

John Healy
, Desmond Chambers

Computer Science

Galway-Mayo Institute of Technology

Research output: Chapter in Book or Conference Publication/Proceeding › Conference Publication › peer-review

2 Citations (Scopus)

Abstract

Although hash-based approaches to sequence alignment and genome assembly are long established, their utility is predicated on the rapid identification of exact k-mers from a hash-map or similar data structure. We describe how a fuzzy hash-map can be applied to quickly and accurately align a prokaryotic genome to the reference genome of a related species. Using this technique, a draft genome of Mycoplasma genitalium, sampled at 1X coverage, was accurately anchored against the genome of Mycoplasma pneumoniae. The fuzzy approach to alignment, ordered and orientated more than 65% of the reads from the draft genome in under 10 seconds, with an error rate of <1.5%. Without sacrificing execution speed, fuzzy hash-maps also provide a mechanism for error tolerance and variability in k-mer centric sequence alignment and assembly applications.

Original language	English
Title of host publication	5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011)
Editors	Miguel Rocha, Juan Corchado Rodriguez, Florentino Fdez-Riverola, Alfonso Valencia
Pages	149-156
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-19914-1_21
Publication status	Published - 2011

Publication series

Name	Advances in Intelligent and Soft Computing
Volume	93
ISSN (Print)	1867-5662

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 3 Good Health and Well-being

Access to Document

10.1007/978-3-642-19914-1_21

Cite this

Healy, J., & Chambers, D. (2011). Fast and accurate genome anchoring using fuzzy hash maps. In M. Rocha, J. Corchado Rodriguez, F. Fdez-Riverola, & A. Valencia (Eds.), 5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011) (pp. 149-156). (Advances in Intelligent and Soft Computing; Vol. 93). https://doi.org/10.1007/978-3-642-19914-1_21

@inproceedings{86e0c9a1c97144a6a56ca610a1ab6c55,

title = "Fast and accurate genome anchoring using fuzzy hash maps",

abstract = "Although hash-based approaches to sequence alignment and genome assembly are long established, their utility is predicated on the rapid identification of exact k-mers from a hash-map or similar data structure. We describe how a fuzzy hash-map can be applied to quickly and accurately align a prokaryotic genome to the reference genome of a related species. Using this technique, a draft genome of Mycoplasma genitalium, sampled at 1X coverage, was accurately anchored against the genome of Mycoplasma pneumoniae. The fuzzy approach to alignment, ordered and orientated more than 65\% of the reads from the draft genome in under 10 seconds, with an error rate of <1.5\%. Without sacrificing execution speed, fuzzy hash-maps also provide a mechanism for error tolerance and variability in k-mer centric sequence alignment and assembly applications.",

author = "John Healy and Desmond Chambers",

year = "2011",

doi = "10.1007/978-3-642-19914-1\_21",

language = "English",

isbn = "9783642199134",

series = "Advances in Intelligent and Soft Computing",

pages = "149--156",

editor = "Miguel Rocha and \{Corchado Rodriguez\}, Juan and Florentino Fdez-Riverola and Alfonso Valencia",

booktitle = "5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011)",

}

Healy, J & Chambers, D 2011, Fast and accurate genome anchoring using fuzzy hash maps. in M Rocha, J Corchado Rodriguez, F Fdez-Riverola & A Valencia (eds), 5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011). Advances in Intelligent and Soft Computing, vol. 93, pp. 149-156. https://doi.org/10.1007/978-3-642-19914-1_21

Fast and accurate genome anchoring using fuzzy hash maps. / Healy, John; Chambers, Desmond.
5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011). ed. / Miguel Rocha; Juan Corchado Rodriguez; Florentino Fdez-Riverola; Alfonso Valencia. 2011. p. 149-156 (Advances in Intelligent and Soft Computing; Vol. 93).

Research output: Chapter in Book or Conference Publication/Proceeding › Conference Publication › peer-review

TY - GEN

T1 - Fast and accurate genome anchoring using fuzzy hash maps

AU - Healy, John

AU - Chambers, Desmond

PY - 2011

Y1 - 2011

N2 - Although hash-based approaches to sequence alignment and genome assembly are long established, their utility is predicated on the rapid identification of exact k-mers from a hash-map or similar data structure. We describe how a fuzzy hash-map can be applied to quickly and accurately align a prokaryotic genome to the reference genome of a related species. Using this technique, a draft genome of Mycoplasma genitalium, sampled at 1X coverage, was accurately anchored against the genome of Mycoplasma pneumoniae. The fuzzy approach to alignment, ordered and orientated more than 65% of the reads from the draft genome in under 10 seconds, with an error rate of <1.5%. Without sacrificing execution speed, fuzzy hash-maps also provide a mechanism for error tolerance and variability in k-mer centric sequence alignment and assembly applications.

AB - Although hash-based approaches to sequence alignment and genome assembly are long established, their utility is predicated on the rapid identification of exact k-mers from a hash-map or similar data structure. We describe how a fuzzy hash-map can be applied to quickly and accurately align a prokaryotic genome to the reference genome of a related species. Using this technique, a draft genome of Mycoplasma genitalium, sampled at 1X coverage, was accurately anchored against the genome of Mycoplasma pneumoniae. The fuzzy approach to alignment, ordered and orientated more than 65% of the reads from the draft genome in under 10 seconds, with an error rate of <1.5%. Without sacrificing execution speed, fuzzy hash-maps also provide a mechanism for error tolerance and variability in k-mer centric sequence alignment and assembly applications.

UR - https://www.scopus.com/pages/publications/80052935774

U2 - 10.1007/978-3-642-19914-1_21

DO - 10.1007/978-3-642-19914-1_21

M3 - Conference Publication

AN - SCOPUS:80052935774

SN - 9783642199134

T3 - Advances in Intelligent and Soft Computing

SP - 149

EP - 156

BT - 5th International Conference on Practical Applications of Computational Biology and Bioinformatics (PACBB 2011)

A2 - Rocha, Miguel

A2 - Corchado Rodriguez, Juan

A2 - Fdez-Riverola, Florentino

A2 - Valencia, Alfonso

ER -

Fast and accurate genome anchoring using fuzzy hash maps

Abstract

Publication series

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this