Longest Repeat Problem: Find the longest repeat in a string.

Question

Although the suffix tree decreases memory requirements from O(|Text|²) to O(|Text|), on average it still requires about 20 times as much memory as Text (when the length of Text is on the order of the human genome). For a 3 GB human genome, 60 GB of RAM is a huge improvement over the 1 TB that we needed to work with a trie constructed for all reads, but it still presents a memory challenge for most machines. This reveals a dark secret of big-O notation, which is that it ignores constant factors. For long strings such as the human genome, we will need to pay attention to this constant factor, since the expression O(|Text|) applies to both an algorithm with 2 · |Text| memory and an algorithm with 1000 · |Text| memory.

Yet before seeing how we can further reduce the memory needed for multiple pattern matching, we ask you to solve three problems showing how suffix trees can be applied to other pattern matching challenges. The first such problem is the Longest Repeat Problem.

Longest Repeat Problem: Find the longest repeat in a string.

1. Input: A string Text.
2. Output: A longest substring of Text that appears in Text more than once.

Code Challenge: Solve the Longest Repeat Problem. (Multiple solutions may exist, in which case you may return any one.)

Sample Input:

ATATCGTTTTATCGTT

Sample Output:

TATCGTT

Heres another dataset to try

TAATGTGCTCATTGAGTTACTTCCACCGCTATGCATGTTCTCACCTGATTCTGGTTGTTCAGTGGCCGGGAATCAGCGATGAGTGACTCTATTCAATGCGGCTAACCTGCCGGTGAAAAAACCGTATCACGAGCCGACTCAGCACGCCCCTTCCAGCCAGTGCTTGCCACGTTTGTATAGTACGCGCACCAGAATCAAATGGACGCTCGTATCGACAACGCCCTCGACCTCTGCGGAACCTGAGGGATACAATGCGACTCTAATGTACACTTCGTCTGGGGGTCATGCATCGTGGCCAAGATCTAGAGTCATCAGTCCCGTAATTTGCCCTACGTGTGAACATCGGTGGTAAGGATATGATGCCTCATCCAAAGCAAGAGCTGAACCAGCACTAAGCGTAGTTGCGCGGGTGTTGAACCTCTCAGCTCATTGGACGCGCAGCAAAGAATGCGTTATCTGTCCCAATCAATAGCAAATTGCGCGATGGGTGGCCCCGACAATTCTGGTTGTTCAGTGGCCGGGAATCAGCGATGAGTGACTCTATTCAATGCGGGAGTTCGTCCGTACTGACTCCCAATTCCATCAATTCTGGTTGTTCAGTGGCCGGGAATCAGCGATGAGTGACTCTATTCAATGCATGGTCGACGACCACCTGGCTGTGTTAAACATCCGATTGTGCGCTTTTTGATTTTCAACATACGCCGGACGGCTAATAAAAACGATGCACGTGCATAATGAGGATATGGGTGCTGTTTTTATGTGCCCGCATTGGCTTGGACCGATCAATATTATGTTGCGATAGGTACCCTGACTCTAAAAGGTCCCATTGGTTTCATTACCGCACGTCGCCACCGTACGTGTCTGAAACCGGTTCGAAGATGTCTGGAGCCAAGTCCATAGGCGTCGTGTATGAGTGGTCATACCGAGCTGCCCATTTGATCCTCTCAAAGGCCGAGAACAGGCACGAGGTGACGCCCTTTTACCTCGTAGACCCAAACACCCAAGTGTCCCCAGGAGCCCTCGCGTACTTAAGCACATCTCCCGCCGCCATGGTACTCTGCGAGTTGGATCATACATACATCACTAGGTAGATGGAAGCATGAGCCAAACCTTACCCCAAATACGCCATAGTAGTGAACGCACTCATGAGTAGAGT

Answer 1

We can't give you source code, because it would defeat the purpose of the exercise. However I have completed this exact problem in the past and would be willing to spend some time with you to understand it and answer it. I have a Bioinformatics BS from UCSC