2
\$\begingroup\$

Here, I am reading in a newline delimited file that can be millions of repeating lines that looks like this:

TGATAGTTAGTCATATGAAAGCATCATTAGTAAACCACATTGCTTATTATATTGAACAGT
TACATCTGGCTTATTATACAAAGAGAAAACCATACTATTCATACTATTCTCTTTTTGATC
TTCTCAATCTTCTGTTGTTAGATATTCTATTCCTTGCTCACCATATATACTACTTATGTC
etc.

The goal is to count the number substring instances within this file, including those substrings that span two lines.

The challenge I have is that the input files can be large, so speed is very desirable. So, I am looking for any good suggestions to improve speed here.

My header:

package main

import ("fmt";"os";"bufio";"compress/gzip";"strings";"time")

This function reads the input file into memory as an array. This takes about 5s on my machine. The input file is newline delimited, so this function iterates through each line of the file and adds each line as a value in the genome array.

func input_file(loc string) []string {
    var genome []string

    // my file is zipped because it can be pretty large
    file, err := os.Open(loc)
    f, err := gzip.NewReader(file)
    check(err)

    // a scanner is a convenient interface to read newline-delimited files
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        genome = append(genome, scanner.Text())
    }

    if err := scanner.Err(); err != nil {
        fmt.Fprintln(os.Stderr, "reading standard input:", err)
    }

    f.Close()
    return genome
}

The above function uses this check for read errors.

func check(e error) {
    if e != nil {
        panic(e)
    }
}

Here I iterate through the array that contains all of the strings read in from the file. This takes about 4s on my machine. It is a bit unfortunate that I am iterating through the file to read it, then iterating through the data a second time to search for substrings. The reason I did this is so that I could reuse the file reading code so, I didn't want it to do anything other than read in the data. I'm sure there is a better way of handling this though.

func search (genome []string, kmers map[string]int64) map[string]int64 {
    left := ""
    right := ""
    full_seq := ""

    // iterate through data pulled from file
    for _, seq := range genome {

        /* maybe not really necessary to understand why i'm doing this but 
        the input file is newline delimited and so i am merging lines 
        together in case a substring overlaps a newline. */
        left = right
        right = seq
        full_seq = left + right

        kmers = contain_kmer(full_seq, kmers) // check for substring
    }
    return kmers
}

This function is called by the search function and looks for all substrings and if they are found, are counted.

func contain_kmer (seq string, kmers map[string]int64) map[string]int64 {
    for k := range kmers {
        if strings.Contains(seq, k) {
            kmers[k] += 1 // if found, add to total count
        }
    }
    return kmers
}

Here is the main function which points to the input file location, reads the file into memory using the input_file function and then searches for substrings using the search function. On my machine, the code takes about 7s to run.

func main() {
    start := time.Now()
    loc := "./myFile.gz" // input file location

    genome := input_file(loc) // read file into memory

    // counts of substrings to be located within input file
    kmers := map[string]int64 {
        "TATTC":0,
        "GTAAACCACATTGCTTATTA":0,
    }

    // locate the substrings
    kmers = search(genome, kmers)
    end := time.Now()

    fmt.Println(kmers) // display counts
    fmt.Println(end.Sub(start))
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

You're reading the file into memory inefficiently. I can't write the full code currently, but here's the gist:

Instead, use the ioutil package: func ReadFile(filename string) ([]byte, error).

Once you've read the file into a byte array, you can remove extraneous characters (newlines, invalid characters, etc). One way is to use bytes.Replace with n of -1.

Then, you can search the byte array using the bytes package: func Count(s, sep []byte) int.


Also, if you want to correctly time a function, use the testing package.

\$\endgroup\$
2
  • \$\begingroup\$ this works really nicely, the only problem I'm having is removing the newlines from the byte array. How do you do this? \$\endgroup\$ Feb 4, 2019 at 19:45
  • \$\begingroup\$ @TheNightman Edited my answer to address this. \$\endgroup\$
    – esote
    Feb 4, 2019 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.