LOCALIZED SUFFIX ARRAY AND ITS APPLICATIONTO GENOME MAPPING PROBLEMS FOR PAIRED-ENDSHORT READS

摘要

We introduce a new data structure, a localized suffix array, based on which occurrenceinformation is dynamically represented as the combination of global positional infor-mation and local lexicographic order information in text search applications. For thesearch of a pair of words within a given distance, many candidate positions that sharea coarse-grained global position can be compactly represented in term of local lexico-graphic orders as in the conventional suffix array, and they can be simultaneously exam-ined for violation of the distance constraint at the coarse-grained resolution. Trade-offbetween the positional and lexicographical information is progressively shifted towardsfiner positional resolution, and the distance constraint is reexamined accordingly. Thusthe paired search can be efficiently performed even if there are a large number of occur-rences for each word. The localized suffix array itself is in fact a reordering of bits insidethe conventional suffix array, and their memory requirements are essentially the same.We demonstrate an application to genome mapping problems for paired-end short readsgenerated by new-generation DNA sequencers. When paired reads are highly repetitive,it is time-consuming to naively calculate, sort, and compare all of the coordinates. For ahuman genome re-sequencing data of 36 base pairs, more than 10 times speedups over thenaive method were observed in almost half of the cases where the sums of redundancies(number of individual occurrences) of paired reads were greater than 2,000.