Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome

Motivation: There is a significant ongoing research to identify the number and types of repetitive DNA sequences. As more genomes are sequenced, efficiency and scalability in computational tools become mandatory. Existing tools fail to find distant repeats because they cannot accommodate whole chrom...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Deymonnaz, A., Heiber, P.
Formato: JOUR
Materias:
article
bioinformatics
computer program
controlled study
gene sequence
genetic algorithm
human
human chromosome
human genome
intermethod comparison
nucleotide repeat
priority journal
Algorithms
Genome, Human
Genomics
Humans
Repetitive Sequences, Nucleic Acid
Homo sapiens
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_13674803_v25_n14_p1746_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_13674803_v25_n14_p1746_Becher
record_format dspace
spelling todo:paper_13674803_v25_n14_p1746_Becher2023-10-03T16:11:32Z Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome Becher, V. Deymonnaz, A. Heiber, P. article bioinformatics computer program controlled study gene sequence genetic algorithm human human chromosome human genome intermethod comparison nucleotide repeat priority journal Algorithms Genome, Human Genomics Humans Repetitive Sequences, Nucleic Acid Homo sapiens Motivation: There is a significant ongoing research to identify the number and types of repetitive DNA sequences. As more genomes are sequenced, efficiency and scalability in computational tools become mandatory. Existing tools fail to find distant repeats because they cannot accommodate whole chromosomes, but segments. Also, a quantitative framework for repetitive elements inside a genome or across genomes is still missing. Results: We present a new efficient algorithm and its implementation as a software tool to compute all perfect repeats in inputs of up to 500 million nucleotide bases, possibly containing many genomes. Our algorithm is based on a suffix array construction and a novel procedure to extract all perfect repeats in the entire input, that can be arbitrarily distant, and with no bound on the repeat length. We tested the software on the Homo sapiens DNA genome NCBI 36.49. We computed all perfect repeats of at least 40 bases occurring in any two chromosomes with exact matching. We found that each H. sapiens chromosome shares ∼10% of its full sequence with every other human chromosome, distributed more or less evenly among the chromosome surfaces. We give statistics including a quantification of repeats by diversity, length and number of occurrences. We compared the computed repeats against all biological repeats currently obtainable from Ensembl enlarged with the output of the dust program and all elements identified by TRF and RepeatMasker (ftp://ftp.ebi.ac.uk/pub/databases/ensembl/ jherrero/.repeats/all_repeats.txt.bz2). We report novel repeats as well as new occurrences of repeats matching with known biological elements. © The Author 2009. Published by Oxford University Press. All rights reserved. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Heiber, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_13674803_v25_n14_p1746_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic article
bioinformatics
computer program
controlled study
gene sequence
genetic algorithm
human
human chromosome
human genome
intermethod comparison
nucleotide repeat
priority journal
Algorithms
Genome, Human
Genomics
Humans
Repetitive Sequences, Nucleic Acid
Homo sapiens
spellingShingle article
bioinformatics
computer program
controlled study
gene sequence
genetic algorithm
human
human chromosome
human genome
intermethod comparison
nucleotide repeat
priority journal
Algorithms
Genome, Human
Genomics
Humans
Repetitive Sequences, Nucleic Acid
Homo sapiens
Becher, V.
Deymonnaz, A.
Heiber, P.
Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
topic_facet article
bioinformatics
computer program
controlled study
gene sequence
genetic algorithm
human
human chromosome
human genome
intermethod comparison
nucleotide repeat
priority journal
Algorithms
Genome, Human
Genomics
Humans
Repetitive Sequences, Nucleic Acid
Homo sapiens
description Motivation: There is a significant ongoing research to identify the number and types of repetitive DNA sequences. As more genomes are sequenced, efficiency and scalability in computational tools become mandatory. Existing tools fail to find distant repeats because they cannot accommodate whole chromosomes, but segments. Also, a quantitative framework for repetitive elements inside a genome or across genomes is still missing. Results: We present a new efficient algorithm and its implementation as a software tool to compute all perfect repeats in inputs of up to 500 million nucleotide bases, possibly containing many genomes. Our algorithm is based on a suffix array construction and a novel procedure to extract all perfect repeats in the entire input, that can be arbitrarily distant, and with no bound on the repeat length. We tested the software on the Homo sapiens DNA genome NCBI 36.49. We computed all perfect repeats of at least 40 bases occurring in any two chromosomes with exact matching. We found that each H. sapiens chromosome shares ∼10% of its full sequence with every other human chromosome, distributed more or less evenly among the chromosome surfaces. We give statistics including a quantification of repeats by diversity, length and number of occurrences. We compared the computed repeats against all biological repeats currently obtainable from Ensembl enlarged with the output of the dust program and all elements identified by TRF and RepeatMasker (ftp://ftp.ebi.ac.uk/pub/databases/ensembl/ jherrero/.repeats/all_repeats.txt.bz2). We report novel repeats as well as new occurrences of repeats matching with known biological elements. © The Author 2009. Published by Oxford University Press. All rights reserved.
format JOUR
author Becher, V.
Deymonnaz, A.
Heiber, P.
author_facet Becher, V.
Deymonnaz, A.
Heiber, P.
author_sort Becher, V.
title Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
title_short Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
title_full Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
title_fullStr Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
title_full_unstemmed Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
title_sort efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome
url http://hdl.handle.net/20.500.12110/paper_13674803_v25_n14_p1746_Becher
work_keys_str_mv AT becherv efficientcomputationofallperfectrepeatsingenomicsequencesofuptohalfagigabytewithacasestudyonthehumangenome
AT deymonnaza efficientcomputationofallperfectrepeatsingenomicsequencesofuptohalfagigabytewithacasestudyonthehumangenome
AT heiberp efficientcomputationofallperfectrepeatsingenomicsequencesofuptohalfagigabytewithacasestudyonthehumangenome
_version_ 1807321115337424896

Ejemplares similares