convert an interval in one of the sequences into an interval in the
    alignment. Alignment intervals are inclusive of start, but not end. They
    are one-based. Hence the full alignment has coords [1, N+1), where N is the
    length of the alignment (number of columns). Sequence coords follow the
    same conventions: one-based, inclusive of start but not end.

    :param seq_name: which sequence are the start and end coords for?
    :param start:    start of the interval in sequence co-ordinates
    :param end:      end of the interval in sequence co-ordinates
    :param trim:     if true, trim coordinates that fall partially outside
                     the sequence
    :raises AlignmentError: if coordinates fall entirely outside the
                            sequence, or partially outside and trim == false

def sequence_to_alignment_coords(self, seq_name, start, end, trim=False):
    """
    convert an interval in one of the sequences into an interval in the
    alignment. Alignment intervals are inclusive of start, but not end. They
    are one-based. Hence the full alignment has coords [1, N+1), where N is the
    length of the alignment (number of columns). Sequence coords follow the
    same conventions: one-based, inclusive of start but not end.

    :param seq_name: which sequence are the start and end coords for?
    :param start:    start of the interval in sequence co-ordinates
    :param end:      end of the interval in sequence co-ordinates
    :param trim:     if true, trim coordinates that fall partially outside
                     the sequence
    :raises AlignmentError: if coordinates fall entirely outside the
                            sequence, or partially outside and trim == false
    """
    # check for valid order of start/end
    if end <= start:
      raise InvalidSequenceCoordinatesError("invalid region: " + str(start) +
                                            ", " + str(end))
    seq = self[seq_name]
    s_start = seq.start
    s_end = seq.end
    pos_strand = seq.is_positive_strand()

    # check that the start and end coords are at least partially in the seq
    if start > s_end or end < s_start:
      msg = "Cannot convert " + str(start) + ", " + str(end) + " to " +\
            "alignment coordinates; falls fully outside of sequence " +\
            str(s_start) + ", " + str(s_end)
      raise InvalidSequenceCoordinatesError(msg)

    # trim overlap if that option is sepcified, otherwise complain if outside
    if trim:
      start = s_start if start < s_start else start
      end = s_end if end > s_end else end
    elif start < s_start or end > s_end:
      msg = "Cannot convert " + str(start) + ", " + str(end) + " to " +\
            "alignment coordinates; falls artially outside of seq. " +\
            str(s_start) + ", " + str(s_end)
      raise InvalidSequenceCoordinatesError(msg)

    num_gaps = 0
    num_non_gaps = 0
    res = []
    current_start = None
    current_end = None
    l_start = 0 if pos_strand else self.size() - 1
    l_end = self.size() if pos_strand else 0
    l_step = 1 if pos_strand else -1
    for i in range(l_start, l_end, l_step):
      if seq[i] == GAP_CHAR:
        num_gaps += 1
      else:
        num_non_gaps += 1

      if num_non_gaps > end - s_start:    # done, past the end of the ROI
        break
      if num_non_gaps > start - s_start:  # within ROI still
        if seq[i] != GAP_CHAR:
          if current_start is None and current_end is None:
            current_start = i
            current_end = i + 1
          else:
            if ((pos_strand and seq[i - 1] == GAP_CHAR) or
                (not pos_strand and seq[i + 1] == GAP_CHAR)):
              # is the start of a new non-gapped region...
              res.append((current_start + 1, current_end + 1))
              current_start = i
              current_end = i + 1
            if pos_strand and seq[i - 1] != GAP_CHAR:
              # is continuation of non-gapped region
              current_end += 1
            if not pos_strand and seq[i + 1] != GAP_CHAR:
              # is continuation of non-gapped region
              current_start -= 1
    res.append((current_start + 1, current_end + 1))
    return res