Transposon detection and clustering algorithms
Repeats, copy languages and computational linguistics
- Bejerano G, Haussler D, Blanchette M. Into the heart of darkness: large-scale clustering of human non-coding DNA. Bioinformatics. 2004 Aug 4;20 Suppl 1:i40-8.
- Start with a graph whose nodes are all putative transposons & edges correspond to BLAST matches
- Apply the following heuristic to break up this graph:
- Split any node whose set of neighbors can be partitioned into two dissimilar subsets
- Iterate, reducing graph to a set of densely-connected subgraphs