@techreport{TR-IC-02-14,
  number = {IC-02-14},
  author = {J. Meidanis and P. Takaki},
  title = {Interval graphs with repeats and the {DNA} fragment assembly problem},
  month = {November},
  year = {2002}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 7 pages.
    \par\selectlanguage{english}\textbf{Abstract}
        The DNA fragment assembly problem is described as
        follows. There is a DNA sequence $Seq[1..L]$, over the
        alphabet $\{A,C,G,T\}$, which is unknown. Fragments are taken
        from $Seq$ and their sequence is directly determined by
        sequencing machines. Each fragment corresponds to an interval
        $[i,j]$ contained in $[1,L]$ and the sequencing machine
        outputs the substring $Seq[i,j]=Seq(i)Seq(i+1)\ldots
        Seq(j)$. Typically the size of interval $[i,j]$, which is
        $j-i+1$, lies in the range $500$ to $1000$, while $L$ is much
        larger; in some cases like, $L=50,000$, but it may reach
        $3,000,000,000$. Given a number of fragments we want to
        determine the string $Seq$. Interval Graphs have been used to
        model this problem, but they do not account for repeats in the
        sequence $Seq$. In this note we introduce a new formalism,
        Interval Graphs with Repeats, to address this issue.
  }
}