search

Benson-Genomics-Lab / TRF

Tandem Repeats Finder: a program to analyze DNA sequences
https://tandem.bu.edu/trf/trf.html
GNU Affero General Public License v3.0
155 stars 26 forks source link

readme

TRF

Tandem Repeats Finder: https://tandem.bu.edu/trf/trf.html
Tandem Repeats Database: http://tandem.bu.edu/cgi-bin/trdb/trdb.exe

Table of Contents

Purpose

A tandem repeat in DNA is two or more adjacent, approximate copies of a pattern of nucleotides. Tandem Repeats Finder is a program to locate and display tandem repeats in DNA sequences. In order to use the program, the user submits a sequence in FASTA format. There is no need to specify the pattern, the size of the pattern or any other parameter. The output consists of two files: a repeat table file and an alignment file. The repeat table, viewable in a web browser, contains information about each repeat, including its location, size, number of copies and nucleotide content. Clicking on the location indices for one of the table entries opens a second browser page that shows an alignment of the copies against a consensus pattern. The program is very fast, analyzing sequences on the order of .5Mb in just a few seconds. Submitted sequences may be of arbitrary length. Repeats with pattern size in the range from 1 to 2000 bases are detected.

This material is based upon work supported by the National Science Foundation under Grant No. CCR-9623532

Reference

Benson G. Tandem repeats finder: a program to analyze DNA sequences. Nucleic Acids Res. 1999; 27(2):573–580. doi:10.1093/nar/27.2.573

Authors

Gary Benson
Yozen Hernandez
Yevgeniy Gelfand
Alfredo Rodriguez

License

Tandem Repeats Finder Copyright (C) 1999-2020 Gary Benson

TRF is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

TRF is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

You should have received a copy of the GNU Affero General Public License along with TRF. If not, see https://www.gnu.org/licenses/.

Pre-compiled Versions

To obtain current and/or earlier, pre-compiled versions of TRF:

Instructions for Compiling

To compile TRF, you will need a C compiler (e.g., gcc, clang) with the standard library installed. We have tested compiling and installing TRF under UNIX-based systems (Linux, macOS) and for Windows under Cygwin/MinGW.

Brief instructions (advanced):

# Check actual version
tar xzvf trf-4.10.0.tar.gz
cd trf-4.10.0
mkdir build
cd build
../configure
make
# To install to system
sudo make install
# To copy binary elsewhere
cp src/trf DESTINATION

If you are cloning the repository, replace the first two lines above with:

git clone https://github.com/Benson-Genomics-Lab/TRF.git
cd TRF

Step by step:

This will:

The file will be called trf (trf.exe on Windows). For backwards compatibility with automated scripts exepcting TRF to follow a certain naming scheme, the installation will also create a symbolic link named trf<version>.<operating system>.exe. For example the file on a linux 64 bit operating system for version 4.10.0 will be called trf4.10.0.linux64.exe.

Testing the Installation

Run the executable on the included test file test_seqs.fasta. (This assumes the executable has been named TRF.):

trf test_seqs.fasta 2 5 7 80 10 50 2000 -l 10

This should produce 9 files:

test_seqs.fasta.2.5.7.80.10.50.2000.summary.html
test_seqs.fasta.s1.2.5.7.80.10.50.2000.1.html
test_seqs.fasta.s1.2.5.7.80.10.50.2000.1.txt.html
test_seqs.fasta.s2.2.5.7.80.10.50.2000.1.html
test_seqs.fasta.s2.2.5.7.80.10.50.2000.1.txt.html
test_seqs.fasta.s3.2.5.7.80.10.50.2000.1.html
test_seqs.fasta.s3.2.5.7.80.10.50.2000.1.txt.html
test_seqs.fasta.s4.2.5.7.80.10.50.2000.1.html
test_seqs.fasta.s4.2.5.7.80.10.50.2000.1.txt.html

Open the summary file in a browser. It will point to the four .html files (without the .txt). Each of those files contains a table describing one TR. Below are the tables as they should appear. It is only necessary to confirm that the files have been created and the tables are present.

test_seqs.fasta.s1.2.5.7.80.10.50.2000.1.html

Indices
Period
Size
Copy
Number
Consensus
Size
Percent
Matches
Percent
Indels
Score
A
C
G
T
Entropy
(0-2)
1--35
7
5.0
7
100
0
70
14
28
28
28
1.95

test_seqs.fasta.s2.2.5.7.80.10.50.2000.1.html

Indices
Period
Size
Copy
Number
Consensus
Size
Percent
Matches
Percent
Indels
Score
A
C
G
T
Entropy
(0-2)
1--84
12
7.0
12
100
0
168
16
41
25
16
1.89

test_seqs.fasta.s3.2.5.7.80.10.50.2000.1.html

Indices
Period
Size
Copy
Number
Consensus
Size
Percent
Matches
Percent
Indels
Score
A
C
G
T
Entropy
(0-2)
1--1225
35
35.0
35
100
0
2450
28
22
20
28
1.98

test_seqs.fasta.s4.2.5.7.80.10.50.2000.1.html

Indices
Period
Size
Copy
Number
Consensus
Size
Percent
Matches
Percent
Indels
Score
A
C
G
T
Entropy
(0-2)
1--10000000
125
80000.0
125
100
0
20000000
32
26
13
27
1.94

Quick Start

The following is a recommended command line to run TRF. Parameters are explained further below. This assumes the executable has been renamed trf.

trf yourfile.fa 2 5 7 80 10 50 2000

Using Command Line Version of Tandem Repeats Finder

Once the program is installed you can run it with no parameters to obtain information on proper usage syntax.

If you installed the program as trf then by typing trf at the command line you will see the following output: 

Please use: trf File Match Mismatch Delta PM PI Minscore MaxPeriod [options]

Where: (all weights, penalties, and scores are positive)
  File = sequences input file
  Match  = matching weight
  Mismatch  = mismatching penalty
  Delta = indel penalty
  PM = match probability (whole number)
  PI = indel probability (whole number)
  Minscore = minimum alignment score to report
  MaxPeriod = maximum period size to report
  [options] = one or more of the following:
        -m        masked sequence file
        -f        flanking sequence
        -d        data file
        -h        suppress html output
        -r        no redundancy elimination
        -l <n>    maximum TR length expected (in millions) (eg, -l 3 or -l=3 for 3 million)

Note the sequence file should be in FASTA format:

>Name of sequence
aggaaacctgccatggcctcctggtgagctgtcctcatccactgctcgctgcctctccag
atactctgacccatggatcccctgggtgcagccaagccacaatggccatggcgccgctgt
actcccacccgccccaccctcctgatcctgctatggacatggcctttccacatccctgtg

The program accepts a minimum of eight parameters. Options can be specified to generate additional files.

The following is a more detailed description of the parameters:

Using recommended parameters the command line will look something like: 

 trf yoursequence.txt 2 7 7 80 10 50 500 -f -d -m

Once the program starts running it will print update messages to the screen. The word "Done" will be printed when the program finishes.

For single sequence input files there will be at least two HTML format output files, a repeat table file and an alignment file. If the number of repeats found is greater than 120, multiple linked repeat tables are produced. The links to the other tables appear at the top and the bottom of each table. To view the results start by opening the first repeat table file with your web browser. This file has the extension ".1.html". Alignment files can be accessed from the repeat table files. Alignment files end with the ".txt.html" extension.

For input files containing multiple sequences a summary page is produced that links to the output of individual sequences. This file has the extension "summary.html". You should start by opening this file if your input had multiple sequences in the same file. Also note that the output files of individual sequences will have an identifier of the form ".sn." ( n an integer) embedded in the name indicating the index of the sequence in the input file. The identifier is omitted for single sequence input files.

For more information on the output please see Table Explanation and Alignment Explanation.

TRF Definitions

FASTA Format:

The FASTA format is a plain text format which looks something like this:

>myseq
AGTCGTCGCTAGCTAGCTAGCATCGAGTCTTTTCGATCGAGGACTAGACTTCTAGCTAGC
TAGCATAGCATACGAGCATATCGGTCATGAGACTGATTGGGCTTTAGCTAGCTAGCATAG
CATACGAGCATATCGGTAGACTGATTGGGTTTAGGTTACC

The first line starts with a greater than sign ">" and contains a name or other identifier for the sequence. This is the sequence header and must be in a single line. The remaining lines contain the sequence data. The sequence can be in upper or lower case letters. Anything other than letters (numbers for example) is ignored. Multiple sequences can be present in the same file as long as each sequence has its own header.

Table Explanation:

The summary table includes the following information:

  1. Indices of the repeat relative to the start of the sequence.
  2. Period size of the repeat.
  3. Number of copies aligned with the consensus pattern.
  4. Size of consensus pattern (may differ slightly from the period size).
  5. Percent of matches between adjacent copies overall.
  6. Percent of indels between adjacent copies overall.
  7. Alignment score.
  8. Percent composition for each of the four nucleotides.
  9. Entropy measure based on percent composition.

If the output contains more than 120 repeats, multiple linked tables are produced. The links to the other tables appear at the top and bottom of each table.

Note: If you save multiple linked summary table files, use the default names supplied by your browser to preserve the automatic linking.

Alignment Explanation:

The alignment is presented as follows:

  1. In each pair of lines, the actual sequence is on the top and a consensus sequence for all the copies is on the bottom.
  2. Each pair of lines is one period except for very small patterns.
  3. The 10 sequence characters before and after a repeat are shown.
  4. Symbol * indicates a mismatch.
  5. Symbol - indicates an insertion or deletion.
  6. Statistics refers to the matches, mismatches and indels overall between adjacent copies in the sequence, not between the sequence and the consensus pattern.
  7. Distances between matching characters at corresponding positions are listed as distance, number at that distance, percentage of all matches.
  8. ACGTcount is percentage of each nucleotide in the repeat sequence.
  9. Consensus sequence is shown by itself.
  10. If chosen as an option, 500 characters of flanking sequence on each side of the repeat are shown.

Note: If you save the alignment file, use the default name supplied by your browser to preserve the automatic cross-referencing with the summary table.

How does Tandem Repeats Finder work?

Probabilistic Model of Tandem Repeats

We model alignment of two tandem copies of a pattern of length n by a sequence of n independent Bernoulli trials (coin-tosses). The probability of success, P(Heads), which we also call PM or matching probability, represents the average percent identity between the copies. Each head in the Bernoulli sequence is interpreted as a match between aligned nucleotides. Each tail is a mismatch, insertion or deletion. A second probability, PI or indel probability, specifies the average percentage of insertions and deletions between the copies. Figure 1 illustrates the underlying idea for the model.

We are interested in the distribution of Bernoulli sequences and the properties of alignments that they represent when dealing with a specific pair (PM, PI), for example, (PM = .80, PI = .10). Note that these conservation parameters serves as a type of extremal bound, i.e., as a quantitative description of the most divergent copies we hope to detect.

Program Outline

The program has detection and analysis components. The detection component uses a set of statistically based criteria to find candidate tandem repeats. The analysis component attempts to produce an alignment for each candidate and if successful gathers a number of statistics about the alignment (percent identity, percent indels) and the nucleotide sequence (composition, entropy measure).

Detection Component

We assume that adjacent copies of any pattern will contain some matching characters in corresponding positions. Just how many matches and how the distance between those matches should vary depend on the fixed values of PM and PI. We use statistical criteria to answer these questions.

The algorithm looks for matching nucleotides separated by a common distance d, which is not specified in advance. For reasons of efficiency it looks for runs of k matches, which we call k-tuple matches. A k-tuple is a window of k consecutive characters from the nucleotide sequence. Matching k-tuples are two windows with identical contents and if aligned in the Bernoulli model would produce a run of k heads. Because we limit ourselves to k-tuple matches, we will not detect all matching characters. For example, if k=6 and two windows contain TCATGT and TCTTGT we will not know that there are 5 matching characters because the window contents are not identical. Put in terms of the Bernoulli model, the aligned windows would be represented by the sequence HHTHHH which is not a run of 6 heads.

The basic operation of the detection component is illustrated in the figure below. Let S be a nucleotide sequence. We select a small integer k, for the tuple or window size (k=5 for example) and keep a list of all possible k-length strings (there are 4k for the DNA alphabet {A,C,G,T}) which we call the probes. By sliding the window across the sequence, we determine the probe at each position i in S. For each probe p, we maintain a history list, Hp, of the positions at which p occurs.

When a position i is added to Hp, we scan Hp for all earlier occurrences of p. Let one earlier occurrence be at j. Since i and j are the indices of matching k-tuples, the distance d=i-j is a possible pattern size for a tandem repeat. For the criteria tests, we need information about other k-tuple matches at the same distance d where the leading tuple occurs in the sequence between j and i. A distance list, Dd, stores this information. It can be thought of as a sliding window of length d which keeps track of the positions of matches and their total.

List Dd is updated every time a match at distance d is detected. Position i of the match is stored on the list and the total is increased. The right end of the window is set to i and matches that occurred before j=i-d are dropped from the list and subtracted from the total. Lists for other nearby distances are also updated at this time (see Random Walk Distribution), but only to reset their right ends to i and remove matches that have been passed by the advancing windows. Information in the updated distance lists is used for the sum-of-heads and apparent-size criteria tests. If both tests are successful, the program moves on to the analysis component.

Statistical Criteria

The statistical criteria are based on runs of heads in Bernoulli sequences, corresponding to matches detected with the k-tuples and stored in the distance lists. The criteria are based on four distributions which depend upon 1) the pattern length, d, 2) the matching probability, PM, 3) the indel probability, PI, and 4) the tuple size, k. For each distribution, we either calculate it with a formula or estimate it using simulation. Then, we select a cutoff value that serves as our criterion.

Sum of Heads Distribution

This distribution indicates how many matches are required for a specific distance or pattern length. Let the random variable Rd,k,PM = the total number of heads in head runs of length k or longer in an iid Bernoulli sequence of length d with success probability PM. The distribution of Rd,k,PM is well approximated by the normal distribution and its exact mean and variance can be calculated in constant time. For the sum-of-heads criterion, we use the normal distribution to determine the largest number, x, such that 95% of the time Rd,k,PM ≥ x. For example, if PM = .75, k = 5 and d = 100, then the criterion is 26. Put another way, if a pattern has length 100 and aligned copies are expected to match in 75 positions, then by counting only matches that fill a window of length 5, we expect to count at least 26 matches 95% of the time.

Random Walk Distribution

This distribution describes how distances between matches may vary due to indels. Because indels change the distance between matching k-tuples (figure below), there will be situations where the pattern has size d, yet the distance between matching k-tuples is d±1, d±2, etc. In order to test the sum-of-heads criterion, we count the matches in Dd±Δd, for Δd = 0,1,...,Δdmax for some Δdmax. In our model, indels are single nucleotide events occurring with probability PI. Insertions and deletions are considered equally likely and we treat the distance change as a problem of random walks. Let the random variable Wd,PI = the maximum displacement from the origin of a one dimensional random walk with expected number of steps equal to PI · d. It can be shown that 95% of the time the random walk ranges between ± 2.3 · √(PI · d). We set Δdmax = floor(2.3 · √(PI · d)). For example if PI = 0.1 and d = 100, then Δdmax* = 7.

Apparent Size Distribution

This distribution is used to distinguish between tandem repeats and non-tandem direct repeats (figure below). For tandem repeats, the leading tuple in matching k-tuples will be distributed throughout the interval from j to i, whereas for non-tandem repeats, they should be concentrated on the right side of the interval near i. Let the random variable Sd,k,PM = the distance between the first and last run of k heads in an iid Bernoulli sequence of length d with success probability PM.

Sd,k,PM is the apparent size of the repeat when using k-tuples to find the matches and will usually be shorter than the pattern size d. We estimate the distribution of Sd,k,PM by simulation because we make it conditional on first meeting the sum-of-heads criterion. For given d, k, and PM, random Bernoulli sequences are generated using PM. For every sequence that meets or exceeds the sum-of-heads criteria, the distance between the first and last run of heads of length k or larger is recorded. From the distribution, we determine the maximum number y such that 95% of the time Sd,k,PM > y. We use y as our apparent size criterion. For example, if PM = .75, k = 5 and d = 100, then the criterion is 56. In order to test the apparent-size criterion, we compute the distance between the first and last tuple on list Dd. If the distance between the tuples is smaller than the criterion, we assume the repeat is not tandem or that we have not yet seen enough of it to be convinced.

Waiting Time Distribution

This distribution is used to pick tuple sizes. Tuple size has a significant inverse effect on the running time of the program because increasing tuple size causes an exponential decrease in the expected number of tuple matches. If the nucleotides occur with equal frequency, then increasing the tuple size by Δk increases the average distance between randomly matching tuples by a factor of 4Δk. If k = 5, the average distance between random matches is approximately 1Kb, but if k = 7, the average distance is approximately 16Kb. Thus, by using a larger tuple size, we keep the history lists short. On the other hand, increasing the tuple size decreases the chance of noticing approximate copies because they may not contain a long, unbroken run of matches. Let the random variable Tk,PM = the number of iid Bernoulli trials with success probability PM until the first occurrence of a run of k successes. Tk,PM follows the geometric distribution of order k. If we let p = PM and q = 1 - p, then the exact probability P(Tk,PM = x) for x ≥ 0 is given by the recursive formula:

For example, if PM = .75 and k = 5 then we need at least 31 trials (coin-tosses) to have a 95% chance of seeing a run of 5 heads. For patterns smaller than 31 characters, we need to use a smaller k-tuple. The waiting time distribution allows us to balance the running time and sensitivity of our algorithm by picking a set of tuple sizes, each applying to a different range of pattern sizes. The program processes the sequence once, simultaneously checking these different tuple sizes. We require that the smallest pattern for tuple size k have a sum-of-heads criterion of at least k+1. The table below shows the range of tuple sizes and the corresponding pattern sizes currently used by the program.

Analysis Component

If the information in the distance list passes the criteria tests, a candidate pattern consisting of positions j+1...i, is selected from the nucleotide sequence and aligned with the surrounding sequence using wraparound dynamic programming (WDP). If at least two copies of the pattern are aligned with the sequence, the tandem repeat is reported. Several implementation details of the analysis component are described below.

Multiple Reporting of Repeat at Different Pattern Sizes :

When a single tandem repeat contains many copies, several pattern sizes are possible. For example, if the basic pattern size is 26, then the repeat may be reported at sizes 26, 52, 78, etc. We limit this redundancy in the output to, at most, three pattern sizes. Note that we do not automatically limit the output to the smallest period size because a much better alignment may come from a larger size.

Narrow Band Alignment :

Alignments are the program's most time intensive calculations. To decrease running time, we limit WDP calculations to a narrow diagonal band in the alignment matrix for patterns larger than 20 characters. In accordance with the random walk results, the band radius is Δdmax. The band is periodically recentered around a run of matches in the current best alignment.

Consensus Pattern and Period Size :

An initial candidate pattern P is drawn from the sequence, but this is usually not the best pattern to align with the tandem repeat. To improve the alignment, we determine a consensus pattern by majority rule from the alignment of the copies with P. The consensus is used to realign the sequence and this final alignment is reported in the output. Period size is defined as the most common matching distance between corresponding characters in the alignment and may not be identical to consensus size.

Redundancy

Tandem Repeats Finder finds repeats for period sizes in the range from 1 to 2000 nucleotides. If a repeat contains many copies, then the same repeat will be detected at various period sizes. This is restricted to the three best scoring period sizes. For example if a tandem repeat has period size 3 and contains 30 copies, then it will most likely also be detected at size 6 with 15 copies and size 9 with 7.5 copies. Also, the same period size may be detected more than once with different scores and slightly different indices.

What's New

New for version 4.10.0

Some of these changes may be present in 4.09 and were undocumented, if they were caught during launch. They are officially present in 4.10.0.

Major:

Minor:

Fixes:

Internal changes:

trf.c:

trfrun.h:

tr30dat.h:

tr30dat.c:

New For Version 4.09 (Feb 22, 2016)

New For Version 4.07b

New For Version 4.04

New For Version 4.03

New For Version 4.00

New For Version 3.21

New For Version 3.20

Previous Update (Version 3.01)

Previous Update (Version 2.02)