BACKGROUND
all higher eukaryotic genomes are rich in multiple classes of repetitive dna.
transposable elements  are particularly abundant, and are the most important factor responsible for genome size variation in both animals and plants  <cit> .
although tes have been judged to be 'junk dna', existing within host genomes as purely selfish denizens  <cit> , it has been found that some repetitive elements perform important roles in their host genomes  <cit> , for instance, as with the telomere-generating het-a and tart retroelements of drosophila  <cit> .
in the last decade, the generation of whole genome sequence data from multiple species has provided the opportunity to investigate the relative contributions of repetitive elements to genomic organization and evolution  <cit> .
tes have been identified in nearly all organisms studied to date.
they are reported to account for 3% of the  <dig> mb yeast genome  <cit> , 20% of the  <dig> mb arabidopsis genome  <cit> , 22% of the  <dig> mb drosophila genome  <cit> , 35% of the  <dig> mb rice genome  <cit> , 15% of the  <dig> mb chicken genome  <cit> , > 60% of the  <dig> mb maize genome  <cit> , 46% of the  <dig> mb human genome  <cit> , > 70% of the  <dig> mb barley genome  <cit>  and > 90% of the  <dig> gb wheat genome  <cit> .
one type of te is the long terminal repeat  retrotransposon .
lrps account for the great majority of the repetitive dna in plant genomes  <cit> .
lrps are named for the ltrs that flank the coding regions of the element.
ltrs contain regulatory sequences important for the proper expression of the lrp, such as the transcription start site and polyadenylation signals.
located between the ltrs of the element are the coding regions that provide the protein products necessary for the element's transposition.
lrps typically contain two open reading frames .
the first of these, gag, contains products necessary for the formation of a virus-like particle where reverse transcription of the rna intermediate takes place.
the second orf, pol, contains the protease, reverse transcriptase, rnase-h and integrase regions necessary for element protein processing, reverse transcription, degradation of the rna intermediate and integration into a new genome location  <cit> .
historically, lrps, other tes and other types of repetitive dna have been identified in a genome by their presence in or near genes, or by the amplification of sequences with homology to tes from other species  <cit> .
due in part to the wealth of sequence information provided by whole genome sequencing projects, the opportunities to detect tes have greatly expanded in recent years.
however, the high cost of completed whole genome sequencing makes this approach inappropriate to investigate the te content of a large number of species.
as interest in tes and other repetitive elements has grown, techniques have been developed to discover and investigate them directly.
without the availability of a large amount of assembled genome sequence, studies focused on the identification of tes within a genome have been restricted to the use of hybridization and pcr techniques  <cit> .
while these methods are useful for the identification of repeats that are highly homologous to already-discovered repeats, they lack the power necessary to discover or precisely quantitate new classes of repetitive dna.
sample sequence analysis, wherein a small amount of dna sequence is generated from randomly selected clones  <cit> , can efficiently provide unbiased genomic information, that could potentially be analyzed for repetitive dna content.
the programs recon  <cit>  and reas  <cit>  have been designed for the de novo discovery of repeats.
recon utilizes assembled genomic sequence as input, while reas was designed for highly redundant genomic coverage with sanger sequence data sets  <cit> .
reas was found to not be adaptable for use with  <dig> sequence data  <cit> .
thus, there is currently no method available that is designed to discover and describe genomic repeats using small quantities of unassembled sanger or  <dig> sequence data.
in order to provide an automated method for the efficient characterization of all of the high copy number repeats within a genome from sparse sample sequence data, the assisted automated assembler of repeat families, or aaarf, algorithm is described in this article.
tests of aaarf on the zea mays genome, using random shotgun sequence data from a sanger sequencing output and from a simulated  <dig> sequence data set are presented.
the z. mays genome has been well studied in terms of repeat content and provides an excellent opportunity to test aaarf's effectiveness.
for both data sets, the program constructed builds representing repeats necessary for genome structure and function  and the seven most abundant lrps in the z. mays genome.
<dig> implementation
<dig>  the aaarf algorithm
aaarf works by comparing sample sequences from a genome to one another via blast  <cit>  and then using a series of blast analyses and multiple alignments to "walk out" an in silico produced molecule, or "build", that represents a discreet family of repeats from the target organism.
a schematic of the aaarf process is shown in figure  <dig>  initially, aaarf accepts a fasta file of sample sequences as input.
an unused sequence  in the dataset is blasted against all other sample sequences.
next, a coverage matrix representing the detected similarities for the sequence is generated based on this blast output.
the coverage matrix is a representation of the coverage depth for each nucleotide position in the sequence being considered.
the coverage matrix is used to assess the repetitive nature of the sample sequence.
the program calculates start and stop points for the sequence that represent the boundaries of a user defined minimum coverage threshold, based on a minimum depth of coverage requirement.
this section of the sequence is known as the minimally covered sequence, or mcs.
if this sequence doesn't meet the minimum coverage requirement, or the mcs is too short, the sequence is rejected and the process starts again with the next sequence in the dataset.
the portion of the sample sequence that corresponds to the mcs is extracted from the sample sequence.
next, the blast output is searched to locate sequences that overlap the mcs in the current search direction .
sequences that meet the minimum coverage requirements and have the potential to extend the process are selected.
a sub-sequence corresponding to the coverage and extension criteria are extracted from the chosen sequences.
a multiple alignment of the selected sequences is performed to generate a consensus sequence called the new query .
the nq is blasted against the mcs to locate the overlap region.
such an overlap indicates that the multiple alignment has produced a sequence that is able to extend the build process correctly.
the overlap region is trimmed from the mcs and the nq is added to the growing build.
to complete a single step, the nq re-enters the loop and is blasted against the sample sequence dataset.
directional extension will continue until either there is insufficient evidence in the coverage matrix to indicate a repetitive sequence or the requirement for a minimum number of sequences to extend the process is not met.
extension then begins from the same starting sequence in the opposite direction.
sample sequences are only allowed to participate in a single build.
this prevents the seeding of additional builds by sequences already used to construct a build.
a sample sequence can participate in both directional extensions of a build in an effort to produce a build that most closely represents a full-length element family.
the size of a single round of extension can be smaller than an individual sample sequence.
to ensure that an entire sample sequence is used in build construction, the user can adjust the number of times that a sequence can be used to extend the build in a given direction.
using the program output along with the sample sequence dataset under investigation, it is possible to locate the biological ends of the elements represented by the builds.
<dig>  program construction input and output
aaarf consists of a single script written in the perl programming language .
the program makes use of a suite of freely available bioperl modules  <cit> .
blast and clustalw  <cit>  are used for sequence comparisons and multiple alignments, respectively.
a single file of fasta sequences and a blast database made from the same sequences, are used as input to the program.
the program produces a fasta file of builds and a diagnostic log file.
the log file is produced with the log4perl module  <cit> , a customizable perl logger.
aaarf's activities during the build process are recorded in this file for later inspection.
aaarf was run on a  <dig> ghz macintosh with  <dig> gb of ram.
analysis of the sanger sequence dataset test was completed in  <dig> minutes , and analysis of the simulated  <dig> dataset was completed in  <dig>  days .
<dig>  build issues
there are a number of potential issues that arise when attempting to construct full-length repetitive elements from sample sequence data.
it is important that these concerns are understood in order to properly implement the aaarf algorithm and interpret its results.
the first of these deals with the internalization and single copy nature of ltrs within a build.
ltrs are arranged at either end of a lrp in a direct repeat orientation.
because aaarf utilizes sequence similarity to construct builds, the two ltrs of a lrp will usually be combined into a single ltr composed of sample sequences from either end of multiple elements.
since it is unlikely that both ltrs of a single lrp will be present in a random set of sample sequences, a build's ltr region will likely be a combination of ltrs from multiple related lrps.
also, because the construction of a build begins at a random point along a repeat , the ltr region will most likely not be present at the end of the build, but internalized within the build.
the next issue to consider is the size of the builds as compared to actual repeats.
aaarf builds may be larger than the corresponding type of native repeat.
it is possible that a full-length copy of the element may be produced for both search directions for a single build.
the number of times that a sequence is allowed to participate in a build are restricted in a given search direction based on the sizes of the sample sequences use as input .
the count is reset at the start of each directional search, allowing for multiple full-length representations to be present in a single build.
this restriction on the number of times that a sequence is used in a search direction ensures that an entire sample sequence is only used once in each build direction.
the parameter controlling the number of times that a sequence can be used to extend a build in a single direction is adjustable by the user.
another way that builds may exceed the size of actual repeats reflects possible size differences within the repeat family.
some families will contain members that are larger than others due to insertions or deletions in certain family members.
as long as the affected member is able to replicate, it will be maintained in the genome, and if it is present at a sufficient copy number, be incorporated into a build.
thus, it is possible that a build may represent the largest members of a family, while the smaller members are also contained within the build.
alternatively, builds may be smaller than native repeats.
in general, it is likely that a build will be shorter than a native lrp by the length of one ltr because of ltr internalization.
a small build will also be produced in any situation where there are not enough sequences present for a particular type of repeat to be assembled by the program.
for instance, ltrs by their nature should be present in numbers at least 2× the amount of sequence for any other region of the element.
since they are present more frequently in the dataset, it is possible that builds representing the ltrs of a family of elements will be produced in cases where construction of the internal regions of the elements is not possible.
also, a build may be broken up due to indels in some family members.
indels can be incorporated into a build as long as there are enough sequences in the dataset to cross the indel-generated build gap.
however, if the indel is large enough that it causes the depth of coverage to drop below the requisite threshold, build construction will stop in that direction.
repeat families may contain levels of sequence diversity that make it impossible for aaarf to assemble all members into a single build.
in this case, it is possible that the family will be broken up into multiple builds.
for nearly all repeat families that aaarf was able to construct in full-length or near full-length form, there were multiple builds for each family .
because of the issues discussed above, it is possible for a build to be fragmented due to low coverage.
if this is the case, then there will be no full-length build for a particular family.
rather, the builds for that family will be present in fragmented form.
it is also possible that sample sequences from regions that differ between members of the same repeat family may initiate their own build.
in this instance there may be a full-length build for a family and additional builds representing regions that were unable to collapse into the full-length build.
in some cases it is possible to resolve build fragmentation issues and identify builds that belong to the same family.
shared sequence similarity among aaarf-produced builds can be used to infer relationships between builds that were not combined because of sequence divergence issues or positional effects of sequence used in the build process.
for the three fragmented builds in the sanger and  <dig> tests, comparison of the builds to one another was able to successfully resolve one of the fragmentation events.
percent genome composition data from meyers et al.
<dig>
xilon percent genome composition from meyers, pers.
comm.
fl = builds representing full-length copies of repeat families, f = builds representing fragmented copies of repeat families, i = incomplete builds
<dig>
RESULTS
<dig>  testing the aaarf algorithm
a wealth of information exists regarding the repeats found in the maize genome , particularly the lrp content  <cit> .
the maize genome is approximately  <dig> mb in size  <cit> , and > 60% of the genome is composed of repetitive dna  <cit> , primarily lrps  <cit> .
in order to ascertain aaarf's effectiveness, a database of known maize genomic repeats was assembled.
this database is a combination of tigr's maize repeat database  <cit>  and a maize repeat database developed by p. san miguel at purdue university .
each of these databases contains the sequences of many different repeat families and individual family members found in maize.
builds produced by aaarf were blasted against this known repeat database to investigate how accurately the builds represent actual genomic repeats and to examine how well the program constructs builds representing distinct families of repeats.
to classify a build as representing a type of known repeat, several criteria were used.
a build was required to be at least  <dig> kb in size, and to have at least one hit with a minimum blast score of  <dig> when compared to the known repeat database.
a score of less than  <dig> was taken as evidence that no useful sequence similarity existed between the build and the known repeat database.
builds were also inspected to ensure that they did not improperly fuse two repeat families.
finally, each build was examined to ensure that it showed similarity to a single family of known repeats over at least 90% of its length.
in this regard, all builds generated by aaarf from the maize data analyzed  were found to be homologous to an already-known maize repeat family, indicating both the quality and comprehensiveness of the tigr and san miguel databases.
the ultimate goal of the aaarf algorithm is to construct the best build possible for a given family of repeats.
how well aaarf is able to accomplish this is dependent on the amount of sequence in the sample data set for a given repeat family.
there are many issues regarding the build process that were considered in the examination of the builds .
a build was classified as full-length only if it showed similarity to the entire length of multiple members of a single discreet repeat family.
<dig>  aaarf analysis of sanger sample sequence data from maize
random unfiltered shotgun sequence reads produced by sanger sequencing for maize are available from tigr  <cit> .
sequences were obtained from tigr in december of  <dig>  we selected the first  <dig>  available sequences from this database for input into aaarf.
this sample sequence dataset totaled  <dig> , <dig> bp , representing  <dig> % of the maize genome .
input sequences were screened for vector content using ncbi's univec database <cit> .
aaarf produced  <dig> builds from the sanger sample sequence dataset described above  and the parameter set described in table  <dig>  of these,  <dig> were chosen for further analysis .
as expected, aaarf assembled builds for non-te repeats, including centromeric repeats, ribosomal repeats and knob repeats.
in addition, builds representing all  <dig> of the most abundant lrp families in the maize genome were constructed .
full-length builds were constructed for the four most abundant families.
builds representing the grande and cinful families were fragmented, such that there was a region missing from each build.
for both grande and cinful, the missing region was assembled intact in additional builds for each family.
for the xilon build, a  <dig> bp portion of the ltr region found in native xilon elements was missing.
thus, aaarf constructed full-length or near full-length builds representing the seven most abundant lrp families in the maize genome.
in all cases, aaarf was able to assemble a build for each of these families that readily identified the repeat family.
for the grande family  the largest build covered 80% of the expected family size.
builds not further analyzed
<dig>   <dig> sequence analysis
<dig> sequence analysis  <cit>  is an emerging high throughput technology that greatly lowers the cost of data generation.
this will facilitate the generation of sample sequence datasets for a wide array of species.
the initial  <dig> sequences had an average length of ~ <dig> bp  <cit> .
in order to test the ability of aaarf to utilize this type of data, a simulated dataset of  <dig> sequences for the maize genome was generated .
sequences were screened for vector content using ncbi's univec database  <cit> .
a total of  <dig>  sequences representing  <dig> , <dig> bp  were used as input.
this dataset represents ~ <dig> % of the maize genome .
the same database of known repeats and the same build classification criteria used for testing the output of the sanger sequence test were used for analyzing the  <dig> sequences.
smaller input sequences cause a variety of build issues stemming from the required blast parameter settings used by aaarf.
because of the reduced size of the input sequences compared to the previous dataset, the number of builds with a total size of less than  <dig> kb was greatly increased.
since aaarf only allows each sample sequence to participate in a single build, builds of less than  <dig> kb in length were rejected.
this ensured that as many sequences as possible were available to the program for each build, instead of being utilized in smaller, ultimately uninformative builds.
despite the inherent difficulties posed by shorter sequences, and the overall reduction in sample sequence dataset size, aaarf generated  <dig> builds that were identified as belonging to known repeat families .
all huck family builds were fragmented in the output, with an approximately  <dig>  kb fragment missing from the largest build.
this fragment was present intact in an additional huck build.
ji and opie were constructed in full-length form.
for the remaining  <dig> families in table  <dig>  only grande was constructed in a large build.
it is possible that the inability of the program to construct the other four elements in a full-length size is due to the  <dig> sample sequence data being only ~64% the size of the sanger sequence dataset.
it is also possible that further parameter optimization for  <dig> data will yield superior results.
as  <dig> sequencing technology continues to develop, the average size of the reads is increasing.
such an increase in sequence size will facilitate their use as input sequences for the aaarf approach.
apart from sequence size issues,  <dig> technology brings with it a new set of issues with regard to reliability statistics and error rates  <cit> .
in particular homopolymers pose specific problems due to the nature of the pyrosequencing technology that  <dig> sequencing employs  <cit> .
precise parameter adjustments to account for these issues can be made with the use of actual  <dig> data.
<dig>   <dig> dataset construction
in order to simulate a  <dig> sequence dataset for maize, all available unfiltered shotgun sequences for the maize genome were downloaded from tigr  <cit> .
at the time of this analysis, there were  <dig>  shotgun sequences in this dataset.
the data were divided into three subsets of  <dig>  sequences each.
to simulate an average read size of  <dig> bp, a subsequence of each read was extracted.
positions 100– <dig>  100– <dig> and 100– <dig> were extracted from all sequences in each set respectively.
the extraction was initiated from the  <dig> bp position for each read to avoid any possible sequencing errors at the end of the read.
only one sequence was extracted from each shotgun read to provide a random sampling.
this produced three datasets composed of  <dig>   <dig> and  <dig> bp sequences.
for each of the three subsets, there were sequences that were not large enough for the extraction process, resulting in a final count of  <dig>  sequences.
<dig>  parameters
aaarf parameters for the sanger sequencing and  <dig> datasets were determined by trial and error in order to examine how changes in the program parameters affected program output.
adjustable parameters for both tests are found in table  <dig>  parameters affecting the required length of blast hits, coverage, extension length and maximum number of times that a sequence is allowed to participate in a search direction were chosen based on the sizes of the sample sequences used for each test.
identity and e-value requirements for both tests were determined by trial and error.
required depth of coverage for a sequence to be classified as repetitive, and the required minimum number of sequences for extension were chosen based on an interpretation of what was necessary to recognize a repetitive sequence.
the presence of a particular sequence in the sample sequence dataset at least  <dig> times was seen as evidence of its repetitive nature.
because of slight positional variation of the coordinates of sequences participating in the aaarf process, it is possible that a sequence that belongs in a build may be rejected due to a difference with required positional parameters generated during mcs construction.
in order to account for this phenomenon, only  <dig> sequences were required for extension.
this did not affect the accuracy of the builds when compared to a test requiring a  <dig> sequence minimum for extension.
for the  <dig> test, the word-size blast parameter for the bl2seq was lowered to  <dig> from the standard  <dig>  during testing it became apparent that the small size of the  <dig> sequences presented problems with the detection of overlap between the new query sequence and the mcs .
reduction in the required word size facilitated overlap detection.
<dig>  end finding
as the name of the program indicates, there is a hands-on component to the aaarf process.
the program assembles builds representing discreet families of genomic repeats while maintaining the correct order and orientation of the elements.
however, the element components are unlikely to be placed in the same end-to-end fashion as a typical element.
this is due to the random starting point for a build.
to alleviate this issue, a method for the identification of the biological element endpoints of lrps for aaarf-produced builds has been developed.
for lrps, the ultimate goal is to locate the ltr region of the build as this region contains both element ends.
initially, blastx is used to locate possible protein coding regions within the build, to narrow the area of the build where the ltr may be found.
next, the build is used in a blast analysis against the sample sequence data set that was used as input for the aaarf program.
this blast provides coverage information for the build.
in addition to facilitating the location of the biological endpoints of the build, this information can be compared to the aaarf-generated diagnostic log file to ensure that all suitable sequences were used to construct a given build.
if sequences are found in this comparison that were not used to construct a build, program parameters can be altered to incorporate these sequences.
the apollo program  <cit>  was used to visualize this comparison .
using this information, it is possible to examine the build for regions that are represented at a greater depth of coverage in the sample sequence dataset .
the region of the build that contains the ltr should be covered by sample sequences at least twice as deeply as the rest of the build.
this is due to the presence of ltrs at either end of a native full-length element and the solo-ltrs present in the genome as a result of partial element removal by unequal recombination.
around this region of increased coverage, the individual sample sequences that cover the region are inspected to locate sequences that are truncated at approximately the same position on the build .
because the ltrs are present on either side of a native full-length element, sample sequences that include the ltr boundaries may include either sequence from the interior of the element or sequence from the genome surrounding the element.
once these possible boundaries are identified, this region is extracted from the build for further inspection.
there are four possible orientations for the ltr region, depending on the orientation and strandedness of the sequence that initiated the build.
the extracted section is then inspected for conserved ltr terminal dinucleotide motifs and the primer binding site and polypurine tract for the element family that has been constructed.
these structures are localized to the ltr region of native lrps and can be used to indicate the presence of an ltr within the build.
for a build representing a full-length element, this information can then be used to manually reconstruct a build with ltrs at either end of the build.
for builds that are less than full-length, this approach will be useful in identifying the ltr region if it is contained in the build.
as a proof of principle, this method was used to identify biological element endpoints for the full-length opie build in the sanger sequence test.
the location of the ltr within the build was verified using actual elements from the known repeat database.
<dig> discussion
aaarf provides an excellent resource for the initial characterization of high copy number repeats in a genome that has been subjected to very limited shotgun sequence analysis.
because of the nature of the aaarf process, the pseudomolecules it produces are "patchwork" representations of native repeat elements.
a multiple alignment of selected overlapping and extending sequences is used for each directional extension.
thus, each step represents sections from actual repeats found in the target genome.
sequence divergence information for actual elements is available via the sample sequences used to construct the pseudomolecule.
by comparing these pseudomolecules to the input sample sequence dataset, information about the evolutionary history of the assembled repeat family and the percent of the target genome composed of that repeat can be determined.
while these tests have focused on aaarf's ability to construct builds representing lrp sequences, the utility of the program extends to the construction of builds representing any high copy number repeat in a genome.
as long as there is sufficient sequence in the sample sequence dataset to represent the repeat, aaarf will construct a build for it.
the parameters used here were developed for use in the maize genome.
depending on the type of sample sequence being used or the species being investigated, it will be necessary to alter the program parameters to produce the most accurate builds possible.
this is the primary reason that the diagnostic test log is produced as a part of the aaarf process.
using this log file, it will be possible to optimize the parameter set for any species under investigation.
<dig>
CONCLUSIONS
as understanding of the prevalence and effects of lrps has increased, it has become apparent that understanding the evolutionary dynamics of lrps both within individual genomes and among different species is necessary for a complete understanding of genome structure and history.
the true utility of the aaarf approach is its ability to facilitate such an understanding.
because aaarf is designed to function on sample sequence data, important information about the te content of a genome can be investigated with a small amount of sequence, making this type of analysis feasible for studies that involve hundreds of species.
<dig> availability and requirements
• project name: assisted automated assembler of repeat families
• project home page:
• operating system: mac os x
• programming language: perl
• other requirements: bioperl  <dig> .
<dig> or higher, bioperl run package  <dig>  or higher, log4perl  <dig>  or higher, ncbi blast  <dig> .
<dig> or higher, clustalw  <dig> .
<dig> or higher
• license: gnu lesser general public license
• restrictions: none
<dig> authors' contributions
jdd co-designed the algorithm, conducted the testing and implementation of the algorithm and drafted the manuscript.
rl co-designed the algorithm and reviewed the manuscript.
jlb conceived the approach, participated in its design, provided valuable guidance and critically edited the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
aaarf algorithm perl script.
this is the aaarf algorithm.
the file can be viewed in a text editor.
examples are bbedit for macintosh and wordpad for windows.
this file is also available at the project homepage .
click here for file
additional file 2
aaarf program documentation.
this is the aaarf algorithm documentation.
the file is intended to aid in the use of the program and provides instructions for its use.
the file can be viewed in a text editor.
examples are bbedit for macintosh and wordpad for windows.
this file is also available at the project homepage .
click here for file

 all higher eukaryotic genomes are rich in multiple classes of repetitive dna. transposable elements are particularly abundant, and are the most important factor responsible for genome size variation in both animals and plants. although tes have been judged to be'junk dna', existing within host genomes as purely selfish denizens, it has been found that some repetitive elements perform important roles in their host genomes, for instance, as with the telomere-generating het-a and tart retroelements of drosophila. in the last decade, the generation of whole genome sequence data from multiple species has provided the opportunity to investigate the relative contributions of repetitive elements to genomic organization and evolution. tes have been identified in nearly all organisms studied to date. they are reported to account for 3% of the mb yeast genome, 20% of the mb arabidopsis genome, 22% of the mb drosophila genome, 35% of the mb rice genome, 15% of the mb chicken genome, > 60% of the mb maize genome, 46% of the mb human genome, > 70% of the mb barley genome and > 90% of the gb wheat genome. one type of te is the long terminal repeat retrotransposon. lrps account for the great majority of the repetitive dna in plant genomes. lrps are named for the ltrs that flank the coding regions of the element. ltrs contain regulatory sequences important for the proper expression of the lrp, such as the transcription start site and polyadenylation signals. located between the ltrs of the element are the coding regions that provide the protein products necessary for the element's transposition. lrps typically contain two open reading frames. the first of these, gag, contains products necessary for the formation of a virus-like particle where reverse transcription of the rna intermediate takes place. the second orf, pol, contains the protease, reverse transcriptase, rnase-h and integrase regions necessary for element protein processing, reverse transcription, degradation of the rna intermediate and integration into a new genome location. historically, lrps, other tes and other types of repetitive dna have been identified in a genome by their presence in or near genes, or by the amplification of sequences with homology to tes from other species. due in part to the wealth of sequence information provided by whole genome sequencing projects, the opportunities to detect tes have greatly expanded in recent years. however, the high cost of completed whole genome sequencing makes this approach inappropriate to investigate the te content of a large number of species. as interest in tes and other repetitive elements has grown, techniques have been developed to discover and investigate them directly. without the availability of a large amount of assembled genome sequence, studies focused on the identification of tes within a genome have been restricted to the use of hybridization and pcr techniques. while these methods are useful for the identification of repeats that are highly homologous to already-discovered repeats, they lack the power necessary to discover or precisely quantitate new classes of repetitive dna. sample sequence analysis, wherein a small amount of dna sequence is generated from randomly selected clones, can efficiently provide unbiased genomic information, that could potentially be analyzed for repetitive dna content. the programs recon and reas have been designed for the de novo discovery of repeats. recon utilizes assembled genomic sequence as input, while reas was designed for highly redundant genomic coverage with sanger sequence data sets. reas was found to not be adaptable for use with sequence data. thus, there is currently no method available that is designed to discover and describe genomic repeats using small quantities of unassembled sanger or sequence data. in order to provide an automated method for the efficient characterization of all of the high copy number repeats within a genome from sparse sample sequence data, the assisted automated assembler of repeat families, or aaarf, algorithm is described in this article. tests of aaarf on the zea mays genome, using random shotgun sequence data from a sanger sequencing output and from a simulated sequence data set are presented. the z. mays genome has been well studied in terms of repeat content and provides an excellent opportunity to test aaarf's effectiveness. for both data sets, the program constructed builds representing repeats necessary for genome structure and function and the seven most abundant lrps in the z. mays genome. implementation the aaarf algorithm aaarf works by comparing sample sequences from a genome to one another via blast and then using a series of blast analyses and multiple alignments to "walk out" an in silico produced molecule, or "build", that represents a discreet family of repeats from the target organism. a schematic of the aaarf process is shown in figure initially, aaarf accepts a fasta file of sample sequences as input. an unused sequence in the dataset is blasted against all other sample sequences. next, a coverage matrix representing the detected similarities for the sequence is generated based on this blast output. the coverage matrix is a representation of the coverage depth for each nucleotide position in the sequence being considered. the coverage matrix is used to assess the repetitive nature of the sample sequence. the program calculates start and stop points for the sequence that represent the boundaries of a user defined minimum coverage threshold, based on a minimum depth of coverage requirement. this section of the sequence is known as the minimally covered sequence, or mcs. if this sequence doesn't meet the minimum coverage requirement, or the mcs is too short, the sequence is rejected and the process starts again with the next sequence in the dataset. the portion of the sample sequence that corresponds to the mcs is extracted from the sample sequence. next, the blast output is searched to locate sequences that overlap the mcs in the current search direction. sequences that meet the minimum coverage requirements and have the potential to extend the process are selected. a sub-sequence corresponding to the coverage and extension criteria are extracted from the chosen sequences. a multiple alignment of the selected sequences is performed to generate a consensus sequence called the new query. the nq is blasted against the mcs to locate the overlap region. such an overlap indicates that the multiple alignment has produced a sequence that is able to extend the build process correctly. the overlap region is trimmed from the mcs and the nq is added to the growing build. to complete a single step, the nq re-enters the loop and is blasted against the sample sequence dataset. directional extension will continue until either there is insufficient evidence in the coverage matrix to indicate a repetitive sequence or the requirement for a minimum number of sequences to extend the process is not met. extension then begins from the same starting sequence in the opposite direction. sample sequences are only allowed to participate in a single build. this prevents the seeding of additional builds by sequences already used to construct a build. a sample sequence can participate in both directional extensions of a build in an effort to produce a build that most closely represents a full-length element family. the size of a single round of extension can be smaller than an individual sample sequence. to ensure that an entire sample sequence is used in build construction, the user can adjust the number of times that a sequence can be used to extend the build in a given direction. using the program output along with the sample sequence dataset under investigation, it is possible to locate the biological ends of the elements represented by the builds. program construction input and output aaarf consists of a single script written in the perl programming language. the program makes use of a suite of freely available bioperl modules. blast and clustalw are used for sequence comparisons and multiple alignments, respectively. a single file of fasta sequences and a blast database made from the same sequences, are used as input to the program. the program produces a fasta file of builds and a diagnostic log file. the log file is produced with the log4perl module, a customizable perl logger. aaarf's activities during the build process are recorded in this file for later inspection. aaarf was run on a ghz macintosh with gb of ram. analysis of the sanger sequence dataset test was completed in minutes, and analysis of the simulated dataset was completed in days. build issues there are a number of potential issues that arise when attempting to construct full-length repetitive elements from sample sequence data. it is important that these concerns are understood in order to properly implement the aaarf algorithm and interpret its results. the first of these deals with the internalization and single copy nature of ltrs within a build. ltrs are arranged at either end of a lrp in a direct repeat orientation. because aaarf utilizes sequence similarity to construct builds, the two ltrs of a lrp will usually be combined into a single ltr composed of sample sequences from either end of multiple elements. since it is unlikely that both ltrs of a single lrp will be present in a random set of sample sequences, a build's ltr region will likely be a combination of ltrs from multiple related lrps. also, because the construction of a build begins at a random point along a repeat, the ltr region will most likely not be present at the end of the build, but internalized within the build. the next issue to consider is the size of the builds as compared to actual repeats. aaarf builds may be larger than the corresponding type of native repeat. it is possible that a full-length copy of the element may be produced for both search directions for a single build. the number of times that a sequence is allowed to participate in a build are restricted in a given search direction based on the sizes of the sample sequences use as input. the count is reset at the start of each directional search, allowing for multiple full-length representations to be present in a single build. this restriction on the number of times that a sequence is used in a search direction ensures that an entire sample sequence is only used once in each build direction. the parameter controlling the number of times that a sequence can be used to extend a build in a single direction is adjustable by the user. another way that builds may exceed the size of actual repeats reflects possible size differences within the repeat family. some families will contain members that are larger than others due to insertions or deletions in certain family members. as long as the affected member is able to replicate, it will be maintained in the genome, and if it is present at a sufficient copy number, be incorporated into a build. thus, it is possible that a build may represent the largest members of a family, while the smaller members are also contained within the build. alternatively, builds may be smaller than native repeats. in general, it is likely that a build will be shorter than a native lrp by the length of one ltr because of ltr internalization. a small build will also be produced in any situation where there are not enough sequences present for a particular type of repeat to be assembled by the program. for instance, ltrs by their nature should be present in numbers at least 2× the amount of sequence for any other region of the element. since they are present more frequently in the dataset, it is possible that builds representing the ltrs of a family of elements will be produced in cases where construction of the internal regions of the elements is not possible. also, a build may be broken up due to indels in some family members. indels can be incorporated into a build as long as there are enough sequences in the dataset to cross the indel-generated build gap. however, if the indel is large enough that it causes the depth of coverage to drop below the requisite threshold, build construction will stop in that direction. repeat families may contain levels of sequence diversity that make it impossible for aaarf to assemble all members into a single build. in this case, it is possible that the family will be broken up into multiple builds. for nearly all repeat families that aaarf was able to construct in full-length or near full-length form, there were multiple builds for each family. because of the issues discussed above, it is possible for a build to be fragmented due to low coverage. if this is the case, then there will be no full-length build for a particular family. rather, the builds for that family will be present in fragmented form. it is also possible that sample sequences from regions that differ between members of the same repeat family may initiate their own build. in this instance there may be a full-length build for a family and additional builds representing regions that were unable to collapse into the full-length build. in some cases it is possible to resolve build fragmentation issues and identify builds that belong to the same family. shared sequence similarity among aaarf-produced builds can be used to infer relationships between builds that were not combined because of sequence divergence issues or positional effects of sequence used in the build process. for the three fragmented builds in the sanger and tests, comparison of the builds to one another was able to successfully resolve one of the fragmentation events. percent genome composition data from meyers et al. xilon percent genome composition from meyers, pers. comm. fl = builds representing full-length copies of repeat families, f = builds representing fragmented copies of repeat families, i = incomplete builds  testing the aaarf algorithm a wealth of information exists regarding the repeats found in the maize genome, particularly the lrp content. the maize genome is approximately mb in size, and > 60% of the genome is composed of repetitive dna, primarily lrps. in order to ascertain aaarf's effectiveness, a database of known maize genomic repeats was assembled. this database is a combination of tigr's maize repeat database and a maize repeat database developed by p. san miguel at purdue university. each of these databases contains the sequences of many different repeat families and individual family members found in maize. builds produced by aaarf were blasted against this known repeat database to investigate how accurately the builds represent actual genomic repeats and to examine how well the program constructs builds representing distinct families of repeats. to classify a build as representing a type of known repeat, several criteria were used. a build was required to be at least kb in size, and to have at least one hit with a minimum blast score of when compared to the known repeat database. a score of less than was taken as evidence that no useful sequence similarity existed between the build and the known repeat database. builds were also inspected to ensure that they did not improperly fuse two repeat families. finally, each build was examined to ensure that it showed similarity to a single family of known repeats over at least 90% of its length. in this regard, all builds generated by aaarf from the maize data analyzed were found to be homologous to an already-known maize repeat family, indicating both the quality and comprehensiveness of the tigr and san miguel databases. the ultimate goal of the aaarf algorithm is to construct the best build possible for a given family of repeats. how well aaarf is able to accomplish this is dependent on the amount of sequence in the sample data set for a given repeat family. there are many issues regarding the build process that were considered in the examination of the builds. a build was classified as full-length only if it showed similarity to the entire length of multiple members of a single discreet repeat family. aaarf analysis of sanger sample sequence data from maize random unfiltered shotgun sequence reads produced by sanger sequencing for maize are available from tigr. sequences were obtained from tigr in december of we selected the first available sequences from this database for input into aaarf. this sample sequence dataset totaled, bp, representing % of the maize genome. input sequences were screened for vector content using ncbi's univec database. aaarf produced builds from the sanger sample sequence dataset described above and the parameter set described in table of these, were chosen for further analysis. as expected, aaarf assembled builds for non-te repeats, including centromeric repeats, ribosomal repeats and knob repeats. in addition, builds representing all of the most abundant lrp families in the maize genome were constructed. full-length builds were constructed for the four most abundant families. builds representing the grande and cinful families were fragmented, such that there was a region missing from each build. for both grande and cinful, the missing region was assembled intact in additional builds for each family. for the xilon build, a bp portion of the ltr region found in native xilon elements was missing. thus, aaarf constructed full-length or near full-length builds representing the seven most abundant lrp families in the maize genome. in all cases, aaarf was able to assemble a build for each of these families that readily identified the repeat family. for the grande family the largest build covered 80% of the expected family size. builds not further analyzed sequence analysis sequence analysis is an emerging high throughput technology that greatly lowers the cost of data generation. this will facilitate the generation of sample sequence datasets for a wide array of species. the initial sequences had an average length of ~ bp. in order to test the ability of aaarf to utilize this type of data, a simulated dataset of sequences for the maize genome was generated. sequences were screened for vector content using ncbi's univec database. a total of sequences representing, bp were used as input. this dataset represents ~ % of the maize genome. the same database of known repeats and the same build classification criteria used for testing the output of the sanger sequence test were used for analyzing the sequences. smaller input sequences cause a variety of build issues stemming from the required blast parameter settings used by aaarf. because of the reduced size of the input sequences compared to the previous dataset, the number of builds with a total size of less than kb was greatly increased. since aaarf only allows each sample sequence to participate in a single build, builds of less than kb in length were rejected. this ensured that as many sequences as possible were available to the program for each build, instead of being utilized in smaller, ultimately uninformative builds. despite the inherent difficulties posed by shorter sequences, and the overall reduction in sample sequence dataset size, aaarf generated builds that were identified as belonging to known repeat families. all huck family builds were fragmented in the output, with an approximately kb fragment missing from the largest build. this fragment was present intact in an additional huck build. ji and opie were constructed in full-length form. for the remaining families in table only grande was constructed in a large build. it is possible that the inability of the program to construct the other four elements in a full-length size is due to the sample sequence data being only ~64% the size of the sanger sequence dataset. it is also possible that further parameter optimization for data will yield superior results. as sequencing technology continues to develop, the average size of the reads is increasing. such an increase in sequence size will facilitate their use as input sequences for the aaarf approach. apart from sequence size issues, technology brings with it a new set of issues with regard to reliability statistics and error rates. in particular homopolymers pose specific problems due to the nature of the pyrosequencing technology that sequencing employs. precise parameter adjustments to account for these issues can be made with the use of actual data. dataset construction in order to simulate a sequence dataset for maize, all available unfiltered shotgun sequences for the maize genome were downloaded from tigr. at the time of this analysis, there were shotgun sequences in this dataset. the data were divided into three subsets of sequences each. to simulate an average read size of bp, a subsequence of each read was extracted. positions 100– 100– and 100– were extracted from all sequences in each set respectively. the extraction was initiated from the bp position for each read to avoid any possible sequencing errors at the end of the read. only one sequence was extracted from each shotgun read to provide a random sampling. this produced three datasets composed of and bp sequences. for each of the three subsets, there were sequences that were not large enough for the extraction process, resulting in a final count of sequences. parameters aaarf parameters for the sanger sequencing and datasets were determined by trial and error in order to examine how changes in the program parameters affected program output. adjustable parameters for both tests are found in table parameters affecting the required length of blast hits, coverage, extension length and maximum number of times that a sequence is allowed to participate in a search direction were chosen based on the sizes of the sample sequences used for each test. identity and e-value requirements for both tests were determined by trial and error. required depth of coverage for a sequence to be classified as repetitive, and the required minimum number of sequences for extension were chosen based on an interpretation of what was necessary to recognize a repetitive sequence. the presence of a particular sequence in the sample sequence dataset at least times was seen as evidence of its repetitive nature. because of slight positional variation of the coordinates of sequences participating in the aaarf process, it is possible that a sequence that belongs in a build may be rejected due to a difference with required positional parameters generated during mcs construction. in order to account for this phenomenon, only sequences were required for extension. this did not affect the accuracy of the builds when compared to a test requiring a sequence minimum for extension. for the test, the word-size blast parameter for the bl2seq was lowered to from the standard during testing it became apparent that the small size of the sequences presented problems with the detection of overlap between the new query sequence and the mcs. reduction in the required word size facilitated overlap detection. end finding as the name of the program indicates, there is a hands-on component to the aaarf process. the program assembles builds representing discreet families of genomic repeats while maintaining the correct order and orientation of the elements. however, the element components are unlikely to be placed in the same end-to-end fashion as a typical element. this is due to the random starting point for a build. to alleviate this issue, a method for the identification of the biological element endpoints of lrps for aaarf-produced builds has been developed. for lrps, the ultimate goal is to locate the ltr region of the build as this region contains both element ends. initially, blastx is used to locate possible protein coding regions within the build, to narrow the area of the build where the ltr may be found. next, the build is used in a blast analysis against the sample sequence data set that was used as input for the aaarf program. this blast provides coverage information for the build. in addition to facilitating the location of the biological endpoints of the build, this information can be compared to the aaarf-generated diagnostic log file to ensure that all suitable sequences were used to construct a given build. if sequences are found in this comparison that were not used to construct a build, program parameters can be altered to incorporate these sequences. the apollo program was used to visualize this comparison. using this information, it is possible to examine the build for regions that are represented at a greater depth of coverage in the sample sequence dataset. the region of the build that contains the ltr should be covered by sample sequences at least twice as deeply as the rest of the build. this is due to the presence of ltrs at either end of a native full-length element and the solo-ltrs present in the genome as a result of partial element removal by unequal recombination. around this region of increased coverage, the individual sample sequences that cover the region are inspected to locate sequences that are truncated at approximately the same position on the build. because the ltrs are present on either side of a native full-length element, sample sequences that include the ltr boundaries may include either sequence from the interior of the element or sequence from the genome surrounding the element. once these possible boundaries are identified, this region is extracted from the build for further inspection. there are four possible orientations for the ltr region, depending on the orientation and strandedness of the sequence that initiated the build. the extracted section is then inspected for conserved ltr terminal dinucleotide motifs and the primer binding site and polypurine tract for the element family that has been constructed. these structures are localized to the ltr region of native lrps and can be used to indicate the presence of an ltr within the build. for a build representing a full-length element, this information can then be used to manually reconstruct a build with ltrs at either end of the build. for builds that are less than full-length, this approach will be useful in identifying the ltr region if it is contained in the build. as a proof of principle, this method was used to identify biological element endpoints for the full-length opie build in the sanger sequence test. the location of the ltr within the build was verified using actual elements from the known repeat database. discussion aaarf provides an excellent resource for the initial characterization of high copy number repeats in a genome that has been subjected to very limited shotgun sequence analysis. because of the nature of the aaarf process, the pseudomolecules it produces are "patchwork" representations of native repeat elements. a multiple alignment of selected overlapping and extending sequences is used for each directional extension. thus, each step represents sections from actual repeats found in the target genome. sequence divergence information for actual elements is available via the sample sequences used to construct the pseudomolecule. by comparing these pseudomolecules to the input sample sequence dataset, information about the evolutionary history of the assembled repeat family and the percent of the target genome composed of that repeat can be determined. while these tests have focused on aaarf's ability to construct builds representing lrp sequences, the utility of the program extends to the construction of builds representing any high copy number repeat in a genome. as long as there is sufficient sequence in the sample sequence dataset to represent the repeat, aaarf will construct a build for it. the parameters used here were developed for use in the maize genome. depending on the type of sample sequence being used or the species being investigated, it will be necessary to alter the program parameters to produce the most accurate builds possible. this is the primary reason that the diagnostic test log is produced as a part of the aaarf process. using this log file, it will be possible to optimize the parameter set for any species under investigation.  as understanding of the prevalence and effects of lrps has increased, it has become apparent that understanding the evolutionary dynamics of lrps both within individual genomes and among different species is necessary for a complete understanding of genome structure and history. the true utility of the aaarf approach is its ability to facilitate such an understanding. because aaarf is designed to function on sample sequence data, important information about the te content of a genome can be investigated with a small amount of sequence, making this type of analysis feasible for studies that involve hundreds of species. availability and requirements • project name: assisted automated assembler of repeat families • project home page: • operating system: mac os x • programming language: perl • other requirements: bioperl. or higher, bioperl run package or higher, log4perl or higher, ncbi blast. or higher, clustalw. or higher • license: gnu lesser general public license • restrictions: none authors' contributions jdd co-designed the algorithm, conducted the testing and implementation of the algorithm and drafted the manuscript. rl co-designed the algorithm and reviewed the manuscript. jlb conceived the approach, participated in its design, provided valuable guidance and critically edited the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 aaarf algorithm perl script. this is the aaarf algorithm. the file can be viewed in a text editor. examples are bbedit for macintosh and wordpad for windows. this file is also available at the project homepage. click here for file additional file 2 aaarf program documentation. this is the aaarf algorithm documentation. the file is intended to aid in the use of the program and provides instructions for its use. the file can be viewed in a text editor. examples are bbedit for macintosh and wordpad for windows. this file is also available at the project homepage. click here for file
higher eukaryotic genomes are typically large, complex and filled with both genes and multiple classes of repetitive dna. these results now indicate that hundreds of higher eukaryotic genomes can be efficiently characterized for the nature, abundance and evolution of their major repetitive dna components. the repetitive dnas, primarily transposable elements, are a rapidly evolving genome component that can provide the raw material for novel selected functions and also indicate the mechanisms and history of genome evolution in any ancestral lineage.
 higher eukaryotic genomes are typically large, complex and filled with both genes and multiple classes of repetitive dna. the repetitive dnas, primarily transposable elements, are a rapidly evolving genome component that can provide the raw material for novel selected functions and also indicate the mechanisms and history of genome evolution in any ancestral lineage. despite their abundance, universality and significance, studies of genomic repeat content have been largely limited to analyses of the repeats in fully sequenced genomes.  in order to facilitate a broader range of repeat analyses, the assisted automated assembler of repeat families algorithm has been developed. this program, written in perl and with numerous adjustable parameters, identifies sequence overlaps in small shotgun sequence datasets and walks them out to create long pseudomolecules representing the most abundant repeats in any genome. testing of this program in maize indicated that it found and assembled all of the major repeats in one or more pseudomolecules, including coverage of the major long terminal repeat retrotransposon families. both sanger sequence and datasets were appropriate.  these results now indicate that hundreds of higher eukaryotic genomes can be efficiently characterized for the nature, abundance and evolution of their major repetitive dna components. 